HDU4081 Qin Shi Huang's National Road System（次小生成树）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 1111
 7 #define INF (1<<30)
 8 int n,G[MAXN][MAXN];
 9 int lowcost[MAXN],nearvex[MAXN],T[MAXN],NT,maxedge[MAXN][MAXN];
10 double prim(){
11     memset(maxedge,0,sizeof(maxedge));
12     for(int i=1; i<n; ++i) lowcost[i]=INF;
13     lowcost[0]=0;
14     nearvex[0]=0;
15     NT=0;
16 
17     double res=0;
18     for(int i=0; i<n; ++i){
19         int u=-1,mincost=INF;
20         for(int v=0; v<n; ++v){
21             if(lowcost[v]!=-1 && lowcost[v]<mincost){
22                 mincost=lowcost[v];
23                 u=v;
24             }
25         }
26 
27         for(int i=0; i<NT; ++i) maxedge[T[i]][u]=maxedge[u][T[i]]=max(maxedge[T[i]][nearvex[u]],mincost);
28         T[NT++]=u;
29 
30         res+=sqrt(mincost);
31         lowcost[u]=-1;
32         for(int v=0; v<n; ++v){
33             if(lowcost[v]!=-1 && lowcost[v]>G[u][v]){
34                 lowcost[v]=G[u][v];
35                 nearvex[v]=u;
36             }
37         }
38     }
39     return res;
40 }
41 int main(){
42     int t,x[MAXN],y[MAXN],p[MAXN];
43     scanf("%d",&t);
44     while(t--){
45         scanf("%d",&n);
46         for(int i=0; i<n; ++i) scanf("%d%d%d",x+i,y+i,p+i);
47 
48         for(int i=0; i<n; ++i){
49             for(int j=i+1; j<n; ++j){
50                 G[i][j]=G[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
51             }
52         }
53         double mst=prim(),res=-1;
54         for(int i=0; i<n; ++i){
55             for(int j=i+1; j<n; ++j){
56                 res=max(res,(p[i]+p[j])/(mst-sqrt(maxedge[i][j])));
57             }
58         }
59         printf("%.2f\n",res);
60     }
61     return 0;
62 }