题目链接：https://vjudge.net/problem/UVALive-5713
题意：给出t组数据，每组数据第一行给出一个n，表示点的数量，接下来n行，每行有三个数字，分别是点的坐标x，y和点的值w。现在我们要用n-1条边来连接这n个点，秦始皇希望这n-1条边的权值之和最小，现在徐福说他可以让其中一条边的权值为0，但是他希望这条边所连接的两点的值之和最大，所以秦始皇决定使A/B的值最大，其中，A是徐福选择的那条边所连接两点的值的和，B是除徐福选择的边之外，其他n-2条边的权值之和，输出最大的A/B。
以下内容是书上面看的。
思路：要使A/B最大，所以A要尽量大，B要尽量小。我们先让B尽量小，所以我们先求出最小生成树的权值之和假设是sum，那么我们只要枚举最小生成树的每一条边，把这条边去掉,假设这条边权值是s，让它变成两棵树，分别在两颗树里面找到值最大的点（假设两个点的值分别是a，b），结果就是max{(a+b)*1.0/(sum-s)}。
对于sum，我们用prime算法计算出来，同时记录每个点的前驱，然后枚举我们所要去掉的边的时候，我们可以用dfs标记，把最小生成树分成两颗树。
看代码吧：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 1005 int n,m,k,t; double map[maxn][maxn],dis[maxn]; int pre[maxn]; double sum; int vis[maxn]; struct node{ double x,y; int w; }point[maxn]; double cal_dis(int i,int j){//计算两点距离 return sqrt(1.0*(point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)); } void prime(){ memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++) dis[i]=INF; dis[1]=0; sum=0; for(int i=1;i<=n;i++){ double min1=INF; int u; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]<min1){ min1=dis[j]; u=j; } } if(min1==INF) return; vis[u]=1; sum+=min1; for(int j=1;j<=n;j++){ if(!vis[j]&&map[u][j]<dis[j]){ dis[j]=map[u][j]; pre[j]=u;//记录点j的前驱 } } } } void DFS(int u){ vis[u]=1; for(int i=1;i<=n;i++){ if(!vis[i]&&pre[i]==u) DFS(i); } } double solve(){ double ans=0; for(int i=1;i<=n;i++){ if(pre[i]==0)//我们选择连接点i和点i的前驱的这条边，如果点i没有前驱continue continue; memset(vis,0,sizeof(vis)); DFS(i);//标记以点i根节点的树（标记为1） double s=map[i][pre[i]];//记录去掉的这条边的权值 int a=0,b=0; for(int j=1;j<=n;j++){ if(vis[j])//属于以点i为根的树 a=max(a,point[j].w); else//属于以点pre[i]为根的树 b=max(b,point[j].w); } ans=max(ans,(a+b)*1.0/(sum-s)); } return ans; } int main() { scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%d",&point[i].x,&point[i].y,&point[i].w); memset(map,0,sizeof(map)); for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ map[i][j]=map[j][i]=cal_dis(i,j); } } prime(); printf("%.2lf ",solve()); } return 0; }