枚举作为magic road的边，然后求出A/B。
A/B得在大概O(1)的时间复杂度求出，关键是B，B是包含magic road的最小生成树。
这么求得：
先在原图求MST，边总和记为s，顺便求出MST上任意两点路径上的最长边d[i][j]。
当(u,v)是magic road时，
如果它在原本的MST上，则B就等于s-原(u,v)的权，而原(u,v)的权其实就是d[u][v]；
如果它不在原本的MST上，则B就等于s-d[u][v]+0。
总之就是一个式子：B=s-d[u][v]。
于是，在原图的MST基础上可以在O(1)的时间复杂度求出任意一边作为magic road的情况下的MST。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1111
#define INF (1<<30)
int n,G[MAXN][MAXN];
int lowcost[MAXN],nearvex[MAXN],T[MAXN],NT,maxedge[MAXN][MAXN];
double prim(){
memset(maxedge,,sizeof(maxedge));
for(int i=; i<n; ++i) lowcost[i]=INF;
lowcost[]=;
nearvex[]=;
NT=; double res=;
for(int i=; i<n; ++i){
int u=-,mincost=INF;
for(int v=; v<n; ++v){
if(lowcost[v]!=- && lowcost[v]<mincost){
mincost=lowcost[v];
u=v;
}
} for(int i=; i<NT; ++i) maxedge[T[i]][u]=maxedge[u][T[i]]=max(maxedge[T[i]][nearvex[u]],mincost);
T[NT++]=u; res+=sqrt(mincost);
lowcost[u]=-;
for(int v=; v<n; ++v){
if(lowcost[v]!=- && lowcost[v]>G[u][v]){
lowcost[v]=G[u][v];
nearvex[v]=u;
}
}
}
return res;
}
int main(){
int t,x[MAXN],y[MAXN],p[MAXN];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=; i<n; ++i) scanf("%d%d%d",x+i,y+i,p+i); for(int i=; i<n; ++i){
for(int j=i+; j<n; ++j){
G[i][j]=G[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
}
double mst=prim(),res=-;
for(int i=; i<n; ++i){
for(int j=i+; j<n; ++j){
res=max(res,(p[i]+p[j])/(mst-sqrt(maxedge[i][j])));
}
}
printf("%.2f\n",res);
}
return ;
}