我先用kruskal求出最小生成树，因为肯定是在最小生成树上断边，那么枚举生成树上每一条边，假设断这条边，然后在生成的两个集合里面再跑一圈dfs寻找人口之和最大的，把它们两个连一起，这样不停更新答案，为啥是错的？ 代码如下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <functional>

using namespace std;
const int N = 1e3 + 10;
typedef double DB;
DB x[N], y[N], p[N];
int s[N];
const DB eps = 1e-9;
int cmp(DB x){
  if(fabs(x) < eps) return 0;
  return x < 0 ? -1 : 1;
}
int FIND(int x){
  return x == s[x] ? x : s[x] = FIND(s[x]);
}
struct st{
  int x, y;
  DB z;
  bool operator < (const st &B)const{
    return cmp(z - B.z) < 0;
  }
}ss[N * N];
DB Kruskal(int n, int m){
  int num = 0;
  DB ans = 0.0;
  vector<vector<pair<int, double> > > g(n + 1);
  vector<int> vec;
  for(int i=0;i<m;i++){
    int u = ss[i].x;
    int v = ss[i].y;
    DB w = ss[i].z;
    u = FIND(s[u]);
    v = FIND(s[v]);
    if(u == v) continue;
    s[u] = v;
    g[ss[i].x].push_back({ss[i].y, w});
    g[ss[i].y].push_back({ss[i].x, w});
    vec.push_back(i);
    num += 1;
    ans += w;
    if(num == n - 1) break;
  }
  double mx = -1.0;
  for(int i=0;i<vec.size();i++){
    int u = ss[vec[i]].x;
    int v = ss[vec[i]].y;
    DB w1 = -1.0;
    DB w2 = -1.0;
    function<void(int, int)> Dfs1 = [&](int u, int fa){
      w1 = max(w1, p[u]);
      for(auto v : g[u]){
        if(v.first == fa) continue;
        Dfs1(v.first, u);
      }
    };
    Dfs1(u, v);
    function<void(int, int)> Dfs2 = [&](int u, int fa){
      w2 = max(w2, p[u]);
      for(auto v : g[u]){
        if(v.first == fa) continue;
        Dfs2(v.first, u);
      }
    };
    Dfs2(v, u);
    mx = max(mx, (w1 + w2) / (ans - ss[i].z));
  }
  return mx;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt;
  cin >> tt;
  while(tt--){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
      cin >> x[i] >> y[i] >> p[i];
      s[i] = i;
    }
    int m = 0;
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        ss[m].x = i;
        ss[m].y = j;
        ss[m].z = hypot(x[i] - x[j], y[i] - y[j]);
        m += 1;
      }
    }sort(ss, ss + m);
    cout << fixed << setprecision(2) << Kruskal(n, m) << '\n';
  }
  return 0;
}