HDU4801——思维，生成树（口糊）

//题意：有坐标图上有N个点，每个点有一个收益，要求修n-1条路联通所有点。现在有一个免单机会 ，即免除一条路的花费，求 max(免除花费的路的两端点的收益和/n-1条路的总花费）
//思路：首先不考虑那条边，我们要使得花费最小，肯定需要求一个最小生成树，然后我们进行枚举遍历求最大值，如果枚举到的边使最小生成树的边，那么直接 sum/MST-该边权值 即可
// 如果不是的话，我们需要 sum/MST-（该边的两个端点在最小生成树中连出去的边的最大值）即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
struct pt {
int x, y, w;
}mp[N];
struct edge {
int x, y; double w;
bool operator <(const edge& temp)const {
return w < temp.w;
}
}ld[N * N];
int T, n, cnt;
int fa[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int con[N][N];
bool use[N * N];
vector<int> op[N];
double kruskal() {
sort(ld + 1, ld + 1 + cnt);
int ct = n; double ans = 0;
for (int i = 1; i <= cnt; i++) {
int a = find(ld[i].x), b = find(ld[i].y);
if (a != b) {
use[i] = true;
con[a][b] = i;//最小生成树边
op[a].push_back(i); op[b].push_back(i);
ans += ld[i].w;
fa[a] = b;
ct--;
}
if (ct == 1) break;
}
return ans;
}
int main() {
cin >> T;
while (T--) {
cnt = 0;
for (int i = 1; i <= N; i++) fa[i] = i;
memset(use, false, sizeof(use));
for (int i = 1; i <= N; i++) op[i].clear();
cin >> n;
for (int i = 1; i <= n; i++) cin >> mp[i].x >> mp[i].y >> mp[i].w;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
ld[++cnt].w = sqrt((mp[i].x - mp[j].x) * (mp[i].x - mp[j].x) + (mp[i].y - mp[j].y) * (mp[i].y - mp[j].y));
ld[cnt].x = i, ld[cnt].y = j;
}
}
double temp = kruskal();
double ans = -1;
for (int i = 1; i <= cnt; i++) {
if (use[i])
ans = max(ans, (mp[ld[i].x].w + mp[ld[i].y].w) / (temp - ld[con[ld[i].x][ld[i].y]].w));
else {
double mess = -1;
for (auto wt : op[ld[i].x]) mess = max(mess, ld[wt].w);
for (auto wt : op[ld[i].y]) mess = max(mess, ld[wt].w);
ans = max(ans, (mp[ld[i].x].w + mp[ld[i].y].w) / (temp - mess));
}
}
printf("%.2lf\n", ans);
}
return 0;
}//以上代码随便糊的