这题说的是n个城市 建路 使他们联通然后 ， 可以使用一条超级的路这条路不计入总长，此时路长度为B， 这条路链接的两个城市人口与和为A+B, 然后计算出最大的A/B
解题
先生成一颗最小生成树，然后 计算出这颗树上每两个节点之间要经过的最长的那条路，然后枚举每两个节点u 个v 求出答案
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string.h>
#include <cmath>
using namespace std;
const int maxn =+;
struct Edge{
int u,v;
double dist;
bool operator <(const Edge &rhs)const{
return dist<rhs.dist;
}
};
vector<Edge>E;
struct point{
int x,y;
}LOC[maxn];
int P[maxn],fa[maxn];
double maxcost[maxn][maxn];
struct ed{
int to; double dist;
};
vector<ed>G[ maxn ];
int fid(int u){
return fa[u]==u? u :( fa[u] = fid( fa[u] ) );
}
vector<int>use;
void dfs(int u, int per,double cost){
for(int i =; i < (int )use.size(); i++){
int v = use[i];
maxcost[u][v] = maxcost[v][u] = max( maxcost[per][v], cost);
}
use.push_back(u);
for(int i =; i < (int)G[u].size() ; i++ ){
ed e = G[u][i];
if(e.to!=per) dfs(e.to,u,e.dist);
}
}
double distends(double x1, double y1, double x2, double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
int cas;
scanf("%d",&cas);
for(int cc =; cc <= cas; ++cc ){
int n;
scanf("%d",&n);
for(int i=; i<n; i++){
scanf("%d%d%d",&LOC[i].x,&LOC[i].y,&P[i]);
G[i].clear(); fa[i] = i;
}
E.clear();
for(int i=; i < n; i++)
for(int j = i+; j < n; j++ ){
double d = distends(LOC[i].x,LOC[i].y, LOC[j].x, LOC[j].y);
E.push_back( (Edge){ i,j,d } );
}
sort(E.begin() , E.end());
double sum_dist=;
int ge=n;
for(int i =; i<(int)E.size(); i++ ){
int u = E[i].u, v = E[i].v;
double dist = E[i].dist;
int fu = fid(u),fv =fid(v);
if(fu != fv){
G[u].push_back( (ed){v,dist} ); G[v].push_back( (ed){u,dist} );
fa[ fu ] = fv;
sum_dist+=dist;
ge--; if(ge==) break;
}
}
memset(maxcost,,sizeof(maxcost));
use.clear();
dfs(,-,0.0);
double ans =;
for(int i =; i<n; i++)
for(int j =i+ ; j<n; j++ ){
double c = 1.0*(P[i]+P[j])/(sum_dist-maxcost[i][j]);
if(ans<c){
ans=c;
}
}
printf("%.2f\n",ans);
}
return ;
}