题意：秦始皇要修路，使得这些路的长度和尽量短。徐福有一个可以消掉路长度的技能，只能用一次。问：
假设A=用法术建的那条路的两端的城市的总人口数，B=除了徐福造的那条路以外的路的总长度，建造的路要使得A/B最大。输出A/B。
思路：
既然要总的路最小，就先求一遍最小生成树，消耗为tot。然后枚举路径，如果这个路径在最小生成树上，就用tot减去这个路径的长度得B；
如果这条路径不在生成树上，那么，假如把这个路径加在树上，可得一环，为了使得B尽量小，为了保持树结构，可以消去这个环中最长的路径。
次小生成树就是可以得到树上任意两点间的最长路径段。然后我一直知道prim的思路，但今天才发现这个n*n的方法还挺有用的。
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <iostream> const int inf = 0x3f3f3f3f; using namespace std; const int maxn = 1009; double g[maxn][maxn]; int p[maxn],X[maxn],Y[maxn]; double maxx[maxn][maxn],dis[maxn]; int fa[maxn]; int mark[maxn]; int cnx[maxn][maxn]; int n; double dt(int i,int j){ return sqrt((X[i] - X[j]) *(X[i] - X[j])*1.0 + (Y[i] - Y[j]) *(Y[i] - Y[j])*1.0); } double prim(){ double res = 0.0; for(int i=1; i<=n; i++) { dis[i] = g[1][i]; mark[i] = false; fa[i] = 1; } mark[1] = true; dis[1] = 0.0; for(int i=1; i<n; i++){ int pos = -1; double minn = 99999999.9; for(int j=1; j<=n; j++){ if(!mark[j]&&dis[j] < minn){ minn = dis[j]; pos = j; } } if(pos==-1)return res; mark[pos] = true; int pre = fa[pos]; res += minn; cnx[pre][pos]=1; cnx[pos][pre]=1; maxx[pos][pre] = maxx[pre][pos] = minn; for(int j=1; j<=n; j++){ if(!mark[j]||j==pos)continue; maxx[j][pos] = max(maxx[j][pre], maxx[pre][pos]); maxx[pos][j] = maxx[j][pos]; } for(int j=1; j<=n; j++){ if(!mark[j] && dis[j] > g[pos][j]){ dis[j] = g[pos][j]; fa[j] = pos; } } } return res; } int main(){ int t; scanf("%d" , & t); while(t--){ scanf("%d", &n); memset(maxx,0,sizeof(maxx)); memset(cnx,0,sizeof(cnx)); for(int i=1; i<=n; i++){ scanf("%d%d%d", &X[i], &Y[i], &p[i]); g[i][i] = 0.0; for(int j=1; j<i; j++){ g[i][j] = dt(i,j); g[j][i] = g[i][j]; } } double tot = prim(); double ans = 0.0; // cout<<"tot"<<tot<<endl; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(i==j)continue; if(cnx[i][j]) ans = max(ans, 1.0*(p[i] + p[j]) /(tot - g[i][j])); else ans = max(ans, 1.0*(p[i] + p[j]) / (tot - maxx[i][j])); } } printf("%.2lf ",ans); } return 0; }