UVALive-5713 Qin Shi Huang's National Road System （次小生成树）

题目大意：有n个城市，要修一些路使得任意两个城市都能连通。但是有人答应可以不计成本的帮你修一条路，为了使成本最低，你要慎重选择修哪一条路。假设其余的道路长度为B，那条别人帮忙修的道路两端城市中的总人口为B，要找一个使A/B最大的方案。

题目分析：先求最小生成树，处理出MST中任意两点之间的最长边。因为别人只答应给修一条路，所以枚举这条路，用这条路替换下一条MST中最长的边（在加入这条路后构成的环中），比较求得A/B的最大值。实际上是把求次小生成树的一些后续操作改改。

代码如下：

# include<iostream>

# include<cstdio>

# include<cmath>

# include<cstring>

# include<algorithm>

using namespace std;

# define REP(i,s,n)  for(int i=s;i<(n);++i)

const int N=1005;

const double inf=1e30;

struct Edge

{

    int to,nxt;

};

Edge e[2*N];

double mp[N][N],dp[N][N],d[N];

int cnt,n,head[N],x[N],y[N],pl[N],pre[N],vis[N];

void read()

{

    scanf("%d",&n);

    REP(i,0,n)  scanf("%d%d%d",x+i,y+i,pl+i);

}

double dist(int xa,int ya,int xb,int yb)

{

    return sqrt((xa-xb)*(xa-xb)*1.0+(ya-yb)*(ya-yb)*1.0);

}

void init()

{

    cnt=0;

    memset(head,-1,sizeof(head));

    REP(i,0,n) REP(j,i+1,n)

        mp[j][i]=mp[i][j]=dist(x[i],y[i],x[j],y[j]);

}

void add(int u,int v)

{

    e[cnt].to=v;

    e[cnt].nxt=head[u];

    head[u]=cnt++;

}

double prim()

{

    REP(i,0,n){d[i]=mp[0][i],pre[i]=-1,vis[i]=0;}

    double res=0.0;

    REP(k,0,n){

        double minn=inf;

        int f=0;

        REP(i,0,n){

            if(vis[i])  continue;

            if(minn>d[i]){

                minn=d[i];

                f=i;

            }

        }

        vis[f]=1;

        res+=d[f];

        REP(i,0,n)  if(!vis[i]&&d[i]>mp[f][i]){

            d[i]=mp[f][i];

            pre[i]=f;

        }

    }

    REP(i,0,n)  if(pre[i]!=-1)

        add(pre[i],i),add(i,pre[i]);

    return res;

}

void dfs(int fr,int to,double v)

{

    vis[to]=1;

    dp[fr][to]=v;

    for(int i=head[to];i!=-1;i=e[i].nxt){

        if(!vis[e[i].to])

            dfs(fr,e[i].to,max(v,mp[to][e[i].to]));

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        read();

        init();

        double MST=prim();

        memset(vis,0,sizeof(vis));

        REP(i,0,n){

            memset(vis,0,sizeof(vis));

            dfs(i,i,0);

        }

        double ans=0.0;

        REP(i,0,n) REP(j,i+1,n){

            double B=MST-dp[i][j];

            double A=pl[i]+pl[j];

            ans=max(ans,A/B);

        }

        printf("%.2lf\n",ans);

    }

    return 0;

}