修建道路使得n个点任意两点之间都可以连通，每个点有都有一定的人口，现在可以免费修一条道路，
A是免费修的道路两端结点的人口之和， B的其它不是免费修道路的长度的总和
要求的是A/B的最短值。
B其实就是最小生成树删除一条边只有的权值之和B。 只要我们知道生成树上任意两点之间的最长边，那么只要在这两点之间修一条边，
然后删除最长边，它还是一棵树。 而已这时候的权值之和是B-maxCost[u][v]
那么 答案就是min{p[u][v] / (B-maxCost[u][v])} , 枚举u，v的时间复杂度是O（n*n）。
至于得到maxCost[u][v] 只要在得到最小生成树之后，一遍dfs就可以求出
求解的方法是：当访问一个新节点时，计算所有已经访问过的结点到这个结点的最小权值
max[u][x] = maxCost[x][u] = max(maxCost[x][fa],edge(u,fa))
u是当前访问的结点，fa是u的父亲， x是所有已经访问过的结点。
（其实就是两个嵌套的循环，只不过是在树上循环罢了）
总的时间复杂度是n*n + e*loge 常数没有计算进去。
n*n和eloge 最大时都是1000多w， 3s的时间，足够了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/* */
const int N = + ;
struct Edge
{
int form, to, p;
double dist;
bool operator<(const Edge&rhs)const
{
return dist < rhs.dist;
}
}a[N*N];
int x[N], y[N], p[N];
int father[N];
double maxCost[N][N];
int p2[N][N];
vector<Edge> g[N];
vector<int> st;
int find(int x)
{
if (x == father[x])
return x;
return father[x] = find(father[x]);
}
double kruskal(int n)
{
double sum = ;
for (int i = ; i < n; ++i)
{
int fx = find(a[i].form);
int fy = find(a[i].to);
if (fx != fy)
{
//记录生成树，用来等下dfs
g[a[i].form].push_back(a[i]);
swap(a[i].form, a[i].to);
g[a[i].form].push_back(a[i]);
sum += a[i].dist;
father[fx] = fy;
}
}
return sum;
} /*
这个dfs其实就是给定一棵树，然后求任意两点之间的最大边权， 因为是任意两点， 那么时间复杂度无疑就是O(n*n)
*/
void dfs(int u, int fa, double dis)
{
if (fa!=-)
for (int i = ; i < st.size(); ++i)
{
int x = st[i];
maxCost[x][u] = maxCost[u][x] = max(maxCost[x][fa], dis);
}
st.push_back(u);
for (int i = ; i < g[u].size(); ++i)
{
int v = g[u][i].to;
if (v == fa) continue;
dfs(v, u, g[u][i].dist);
}
}
int main()
{
int t, n, cnt;
double B;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
cnt = ;
st.clear();
for (int i = ; i < n; ++i)
{
father[i] = i;
g[i].clear();
scanf("%d%d%d", &x[i], &y[i], &p[i]);
}
for (int i = ; i < n; ++i)
{
for (int j = i + ; j < n; ++j)
{
p2[i][j] = p2[j][i] = p[i] + p[j];
//边集数组
a[cnt].form = i;
a[cnt].to = j;
a[cnt].p = p[i] + p[j];
a[cnt++].dist = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}
}
sort(a, a + cnt);
B = kruskal(cnt);
dfs(, -, );
double ans = ; //枚举在哪两个之间建免费的道路
for (int i = ; i < n; ++i)
for (int j = i + ; j < n; ++j)
ans = max(ans, p2[i][j] / (B - maxCost[i][j]));
printf("%.2lf\n", ans);
}
return ;
}