prim + 邻接矩阵储存两点间最大距离，然后枚举即可。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<map> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 1010,INF = 0x3f3f3f3f; int fa[maxn],n; vector<int> son[maxn]; int x[maxn],y[maxn],pop[maxn]; double maxr[maxn][maxn];//最小生成树中两点间的最大边 double sum,ans; double e[maxn][maxn]; struct Edge{ int to,from; double val; bool operator < (const Edge &x) const{ return val < x.val; } }; int getfa(int x){ if (fa[x] == x) return x; else return fa[x] = getfa(fa[x]); } inline double pf(double x){ return x * x; } inline double getdis(int u,int v){ return sqrt(pf(x[u] - x[v]) + pf(y[u] - y[v])); } void buildEdge(){ for(int i = 1;i <= n;++i) for(int j = i+1;j <= n;++j){ double dis = getdis(i, j); e[i][j] = e[j][i] = dis; } } void prim() { bool vis[maxn] = {}; double dist[maxn] = {}; for(int i = 1;i <= n;++i) { dist[i] = INF; } vector<int> v; int now = 1; int pre[maxn] = {}; sum = 0; vis[1] = true; dist[1] = 0; v.push_back(1); for(int i = 1;i < n;++i) { for(int j = 1;j <= n;++j) { if(!vis[j] && e[now][j] < dist[j]){ pre[j] = now; dist[j] = e[now][j]; } } double mi = INF; int k = i; for(int j = 1;j <= n;++j) { if(!vis[j] && dist[j] < mi) { mi = dist[j]; k = j; } } sum += dist[k]; now = k; vis[k] = 1; for(int j = 0;j < v.size();++j) { maxr[v[j]][k] = maxr[k][v[j]] = max(maxr[v[j]][pre[k]],dist[k]); } v.push_back(k); } } void solve(){ double ans = 0; for(int i = 1;i <= n;++i) for(int j = i + 1;j <= n;++j){ double A = pop[i] + pop[j]; double B = sum - maxr[i][j]; ans = max(ans,A/B); } printf("%.2f\n",ans); } void init(){ cin >> n; for(int i = 1;i <= n;++i){ cin >> x[i] >> y[i] >> pop[i]; } memset(maxr,0,sizeof maxr); for(int i = 1;i <= n;++i) { for(int j = i + 1;j <= n;++j) e[i][j] = e[j][i] = INF; } buildEdge(); prim(); solve(); } int main(){ int t; cin >> t; while(t--){ init(); } }