UVA 5713 Qin Shi Huang's National Road System

题解：

类似最小生成树，先做最小生成树然后枚举顶点，删边和加边。

[cpp]
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010*1010;
struct NODE{
    int u,v;
    double w;
    bool operator < (const NODE &a) const
    {
        return a.w>w;
    }
}node[maxn*2],in[1005];

struct TREE
{
    int u,next;
    double w;
}tree[maxn*5];
int head[1010];
bool vis[1010];
int f[1005];
double g[1010][1010];
int find(int x)
{
    return f[x]==x? x:f[x]=find(f[x]);
}
int val[1005];
void dfs(int root,int x)
{
    vis[x]=true;
    for(int i=head[x];i!=-1;i=tree[i].next)
    if(!vis[tree[i].u])
    {
        g[root][tree[i].u]=max(tree[i].w,g[root][x]);
        dfs(root,tree[i].u);
    }
}
void kruskal(int n,int e)
{
    memset(head,-1,sizeof(head));
    double sum=0,ans=0;
    int p=0;
    for(int i=0;i<=n;i++)    f[i]=i;
    sort(node,node+e);

    for(int i=0;i<e;i++)
    {
        int x=find(node[i].u);
        int y=find(node[i].v);
        if(x!=y)
        {
            sum+=node[i].w;
            f[y]=x;

            //tree
            tree[p].u=node[i].u;tree[p].w=node[i].w;
            tree[p].next=head[node[i].v];head[node[i].v]=p++;
            tree[p].u=node[i].v;tree[p].w=node[i].w;
            tree[p].next=head[node[i].u];head[node[i].u]=p++;
        }
    }

    for(int i=0;i<=n;i++)
     for(int j=0;j<=n;j++)
      g[i][j]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        vis[j]=false;
        dfs(i,i);
    }

    //g[i][j]

    for(int i=1;i<=n;i++)
     for(int j=i+1;j<=n;j++)
        ans=max(ans,(val[i]+val[j])/(sum-g[i][j]));

    printf("%.2f\n",ans);
}
int main()
{
    int ca,n,num;
    int x[1005],y[1005];
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d",&n);
        num=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&val[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                node[num].u=i;
                node[num].v=j;
                node[num].w=sqrt(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j])));
                num++;
            }
        }
        kruskal(n,num);
    }
    return 0;
}

补充：软件开发 , C++ ,