题目链接
题目大意：
秦始皇要在n个城市之间修筑一条道路使得任意两个城市均可连通。有个道士可以用法力帮忙修一条路。秦始皇希望其他的道路总长B最短且用法术连接的两个城市的人口之和A尽量大，因此下令寻找一个A / B的最大方案。
solution：这道题换个问法就是：在o(1),时间内求出最小生成树删去一条边后的权值。
我们可以先求出最小生成树的权值 minlen， 再o(n^2)求出节点间最小瓶颈路mx[u][v]，那么原题中 B=minlen-mx[u][v], 再枚举u，v算出 A 就可以求出答案max（A/B ）了。
如何求每对节点间最小瓶颈路 ？？
先介绍几个概念
1.最小瓶颈生成树：给出加权无向图，求一颗生成树使得最大边权值尽量小。
怎么求？
我们先把边排序，然后从小到大，如果该边的两个节点没有被连通，那么就把它们加入生成树中。这个过程。。。就是Kruskal呀。 ====> 最小生成树就是最小瓶颈生成树
2.最小瓶颈路：给出加权无向图的两个节点u，v， 求出u到v的路径中最长边的最小值。
怎么搞？？
先求出最小瓶颈生成树，在求u，v在最小瓶颈生成树上的路径的最长边。
3.每对节点的最小瓶颈路： 就是每对节点( u, v )之间的最小瓶颈路
显然，我们可以先求出最小生成树，再用dfs搞。
令： x为所有访问过的节点， u为当前节点， fa为当前节点的父亲节点
则有 mx[u][x]=mx[x][u]=max(mx[x][fa],w[x][fa])
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;
struct P{int x, y;int num;
}p[N];
struct E{int u, v;double dis;
}e[N*N];
struct Edge{int u, v;double w;Edge(int u,int v,double w):u(u),v(v),w(w){}
};
vector<Edge> edges;
vector<int> G[N];
int n, m;void addeage(int u, int v, double w){edges.push_back(Edge(u,v,w));int k=edges.size();G[u].push_back(k-1);
}int pa[N];
int find(int x){int r=x;while( r!=pa[r] ) r=pa[r];int i=x, j;while( i!=pa[i] ){j=pa[i];pa[i]=r;i=j;}return r;
}bool merge(int x, int y){x=find(x), y=find(y);if( x==y ) return false;pa[x]=y; return true;
} double minlen;
double mx[N][N];
vector<int> nodes;
bool cmp(E a, E b){return a.dis<b.dis;
}
void Kruskal(){int em=0;for ( int i=1; i<=n; i++ )for ( int j=i+1; j<=n; j++ ){e[em].u=i, e[em].v=j;e[em++].dis=sqrt( (double)(p[i].x-p[j].x)*(p[i].x-p[j].x) + (double) (p[i].y-p[j].y)*(p[i].y-p[j].y) );}sort(e,e+em,cmp);int num=0;minlen=0;for ( int i=1; i<=n; i++ ) pa[i]=i;for ( int i=0; i<em; i++ )if( merge(e[i].u,e[i].v) && num<n-1 ){num++;minlen+=e[i].dis;addeage(e[i].u,e[i].v,e[i].dis);addeage(e[i].v,e[i].u,e[i]. dis);}
}void dfs(int u, int fa, double dis){for ( int i=0; i<nodes.size(); i++ ){int id=nodes[i];mx[u][id]=mx[id][u]=max(mx[fa][id],dis);}nodes.push_back(u);for ( int i=0; i<G[u].size(); i++ ){Edge ee=edges[G[u][i]];if( ee.v==fa ) continue;dfs(ee.v,u,ee.w);}
}int main(){int T;scanf("%d", &T );while( T-- ){scanf("%d", &n );edges.clear();for ( int i=1; i<=n; i++ ) G[i].clear();nodes.clear();memset(mx,0,sizeof(mx));for ( int i=1; i<=n; i++ ){int x1, x2, x3;scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].num );} Kruskal();dfs(1,0,0);double ret=-1;for ( int i=1; i<=n; i++ )for ( int j=i+1; j<=n; j++ ){ret=max(ret,(double)(p[i].num+p[j].num)/(minlen-mx[i][j]));}printf("%.2lf\n",ret); }
}