【题意】
秦始皇要在n个城市之间修路，而徐福声可以用法术位秦始皇免费修1条路，每个城市还有人口数，现要求徐福声所修之路的两城市的人口数之和A尽量大，而使n个城市互通需要修的路长B尽量短，从而使得A/B最大。问A/B最大是多少？（1000个城市）
Input
The first line contains an integer t meaning that there are t test cases (t ≤ 10).
For each test case:
The first line is an integer n meaning that there are n cities (2 < n ≤ 1000).
Then n lines follow. Each line contains three integers X, Y and P (0 ≤ X, Y ≤ 1000, 0 < P <
100000). (X, Y ) is the coordinate of a city and P is the population of that city.
It is guaranteed that each city has a distinct location.
Output
For each test case, print a line indicating the above mentioned maximum ratio A/B. The result should
be rounded to 2 digits after decimal point.
Sample Input
2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40
Sample Output
65.00
70.00
【分析】
枚举法术边，然后目标就是剩下的路长度最小，并且要形成生成树。
普通的做法就是每一次枚举都做一遍，那样就是n^3(排序可以只排一次)。但是其实可以预处理之后再求的。就是一条边置为0之后的最小生成树，这棵树与删边加一起一定构成一个环，我们用这条边代替一条边，必然选择这个环的最大边，预处理maxcost[u][v]表示u，v在生成树上的路径的最大边，然后直接求ans就好了啦~
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 1100
#define Maxm 1000010 struct node
{
int x,y,next;
double c;
};
node t[Maxn*],tt[Maxn],t2[Maxm];
int len,ln,n; int first[Maxn],fa[Maxn];
double mc[Maxn][Maxn];
bool np[Maxn]; int myabs(int x) {return x<?-x:x;}
// int mymax(int x,int y) {return x>y?x:y;}
double mymax(double x,double y) {return x>y?x:y;} void ins(int x,int y,double c)
{
t[++ln].x=x;t[ln].y=y;t[ln].c=c;
t[ln].next=first[x];first[x]=ln;
} bool cmp(node x,node y) {return x.c<y.c;} int ffind(int x)
{
if(fa[x]!=x) fa[x]=ffind(fa[x]);
return fa[x];
} void dfs(int x,int f,double l)
{
for(int i=;i<=n;i++) if(np[i])
mc[i][x]=mc[x][i]=mymax(mc[i][f],l);
np[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
dfs(t[i].y,x,t[i].c);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d%lf",&tt[i].x,&tt[i].y,&tt[i].c);
len=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
double nx=(double)(tt[i].x-tt[j].x),ny=(double)(tt[i].y-tt[j].y);
t2[++len].x=i;t2[len].y=j;t2[len].c=sqrt(nx*nx+ny*ny);
// ins(i,j,sqrt(nx*nx+ny*ny));
}
for(int i=;i<=n;i++) fa[i]=i;
double sum=;
ln=;memset(first,,sizeof(first));
sort(t2+,t2++len,cmp);
for(int i=;i<=len;i++)
{
if(ffind(t2[i].x)!=ffind(t2[i].y))
{
fa[ffind(t2[i].x)]=ffind(t2[i].y);
ins(t2[i].x,t2[i].y,t2[i].c);ins(t2[i].y,t2[i].x,t2[i].c);
sum+=t2[i].c;
}
if(ln==*(n-)) break;
}
memset(mc,,sizeof(mc));
memset(np,,sizeof(np));
dfs(,,);
double ans=;
for(int i=;i<=len;i++)
{
double A=tt[t2[i].x].c+tt[t2[i].y].c;
if(A*1.0/(sum-mc[t2[i].x][t2[i].y])>ans)
ans=A*1.0/(sum-mc[t2[i].x][t2[i].y]);
}
printf("%.2lf\n",ans);
}
return ;
}
2016-10-31 21:44:35