题意:有n个点，n-1条边。现在徐福可以让一条边无消耗建立，即魔法边。B表示除魔法边之外的的其他边的消耗值和，A表示这条魔法边相连的2个集合中都选一点，
这两点的最大值，现在要求A/B最大。
方法:因为2个值都在变，所以不能贪心。考虑枚举边的情况。由于直接枚举边太多，可以先考虑让B变小，因为A相比来说是可控的。B很容易就想到是最小生成树里面的边。
先求一遍最小生成树，得到minMST值。枚举删除生成树上的边。由于删除生成树上的边后，变成2棵子树（由于删除生成树上的边，所以B<minMST），然后选出2棵子树的最大A值，枚举即可。
#include<stdio.h> #include<string.h> #include<stack> #include<math.h> #include<algorithm> using namespace std; const int maxn = 1010; struct point { int x; int y; int people; int flag; }temp[maxn]; struct node { int x; int y; double v; }a[maxn*maxn]; int n,pa[maxn],cnt; node s[maxn*maxn]; int cou; bool cmp(node a,node b) { return a.v<b.v; } bool cmp1(point a,point b) { return a.people>b.people; } double dist(point fa,point fb) { return sqrt((double)(fa.x-fb.x)*(fa.x-fb.x)+(fa.y-fb.y)*(fa.y-fb.y)); } void init() { for(int i=0;i<=n;i++) pa[i]=i; } int find(int x) { if(x!=pa[x]) pa[x]=find(pa[x]); return pa[x]; } double kruskal() { double sum=0; int i,j; for(i=1;i<cnt;i++) { int fx=find(a[i].x); int fy=find(a[i].y); if(fx!=fy) { pa[fx]=fy; sum+=a[i].v; s[cou]=a[i]; cou++; } } return sum; } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d%d",&temp[i].x,&temp[i].y,&temp[i].people); temp[i].flag=i; } cnt=1; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { a[cnt].x=i; a[cnt].y=j; a[cnt++].v=dist(temp[i],temp[j]); } } init(); sort(a+1,a+cnt,cmp); cou=0; double sum=kruskal(); double ans=0; sort(temp+1,temp+n+1,cmp1); for(i=0;i<cou;i++) { sum-=s[i].v; init(); for(j=0;j<cou;j++) { if(i==j)continue; int fx=find(s[j].x); int fy=find(s[j].y); if(fx!=fy) { pa[fx]=fy; } } for(j=2;j<=n;j++) { if(find(temp[j].flag)!=find(temp[1].flag)) { if((temp[j].people+temp[1].people)*1.0/sum>ans) ans=(temp[j].people+temp[1].people)*1.0/sum; } } sum+=s[i].v; } printf("%.2lf\n",ans); } }
原文：http://www.cnblogs.com/sweat123/p/4947967.html