题目地址：http://acm.hust.edu.cn/vjudge/problem/24956
次小生成树，关键是求MaxVal数组：MaxVal[u][v]保存uv点之间在mst中的边最长的边的长度
1）先求一棵MST，利用Prim算法，且在求的时候求出MaxVal数组，
更新MaxVal方法如下：
prim算法中，已经加入生成树的点集合为W
? 往W新增点s时，设 u 属于W,且 s是被连接到W中的v点的，
? 则
? Max_val[v][s] = 边(v,s)的权
? Max_val[u][s] = Max( Max_val[v][s], Max_val[u][v])
2）枚举u点v点，A就是population[u]+population[v], B即修改图后的权值就等于 mst的中权值-MaxVal[u][v]
代码如下：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=1000000000;
const int maxn=1000+5;
struct City{int x,y,pop;City(int x,int y,int p):x(x),y(y),pop(p){}
};
vector<City> cities;
struct Edge{int from,to;double w;Edge(int f,int t,double w):from(f),to(t),w(w){}bool operator < (const Edge& e) const {return w>e.w;}
};
double G[maxn][maxn];
double getdist(int i,int j){City x=cities[i],y=cities[j];return hypot(x.x-y.x,x.y-y.y);
}
void getEdge(int n)
{for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){double d=getdist(i,j);G[i][j]=G[j][i]=d;}
}
double MaxVal[maxn][maxn];
double Prim(int n) //返回mst的最小权值
{memset(MaxVal,0,sizeof(MaxVal));vector<double> dist(n,INF);vector<bool> used(n,false);vector<int> mst;priority_queue<Edge> Q;double TotW=0;Q.push(Edge(0,0,0));while(mst.size()<n&&!Q.empty()){Edge e=Q.top(); Q.pop();while(used[e.to]&&!Q.empty()) e=Q.top(),Q.pop();if(used[e.to]) continue;TotW+=e.w;int s=e.to;int v=e.from;MaxVal[s][v]=MaxVal[v][s]=G[v][s];for(int i=0;i<mst.size();i++){int u=mst[i];MaxVal[u][s]=max(MaxVal[v][s],MaxVal[u][v]);MaxVal[s][u]=max(MaxVal[s][v],MaxVal[v][u]); //因为是无向边，所以MaxVal[u][v]=MaxVal[v][u] }used[s]=true; mst.push_back(s);for(int v=0;v<n;v++){if(v==s) continue;double w=G[s][v];if(!used[v]&&dist[v]>w){dist[v]=w;Q.push(Edge(s,v,w));}}}double ans=0;for(int u=0;u<n;u++)for(int v=u+1;v<n;v++){int A=cities[u].pop+cities[v].pop;ans=max(ans,A/(TotW-MaxVal[u][v]));}return ans;
}
int main()
{int T,n;cin>>T;while(T--){ int x,y,p;cin>>n;cities.clear();for(int i=0;i<n;i++){cin>>x>>y>>p;cities.push_back(City(x,y,p));}getEdge(n);printf("%.2lf\n",Prim(n));}return 0;
}