UVA 5713 Qin Shi Huangs 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; 
}