https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3714
题目大意：
秦始皇要在n个城市之间修筑一条道路使得任意两个城市均可连通。有个道士可以用法力帮忙修一条路。秦始皇希望其他的道路总长B最短且用法术连接的两个城市的人口之和A尽量大，因此下令寻找一个A / B的最大方案。
思路：
先求出MST，然后枚举用法术修哪一条边。那么，法术修的边显然应该是MST中连接两个点 u ,v中最大的一条边。
所以对MST使用DFS，当访问一个新结点cur时候，考虑所有已经访问过的老结点x，更新f(x,u)=max( f(x,v) ,w(u,v) );其中v是u的老结点。
这样，枚举任意的两个城市，ans = max(ans, (p[i].num+p[j].num) / (mstlen - dp[i][j])); p[i].num为城市i人数，mstlen为最小生成树的长度，dp[i][j]就是上面说的连接i 和j 最大的一条边。
下次直接用vector的了，好多的len什么的。。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1000+10;
int n;
int p_len,e_len,len,n_len;//点的数目，各个点距离的数目，MST的邻接表边数，dfs的顶点数
int fa[MAXN],head[MAXN],nodes[MAXN];
double dp[MAXN][MAXN],mstlen;
int find(int cur)
{
return cur==fa[cur]? cur : fa[cur]=find(fa[cur]);
}
struct point //记录各个城市的坐标和人口
{
int x,y;
int num;
}p[MAXN];
struct edge //化坐标为距离求MST
{
int from,to;
double dis;
bool operator<(const edge &x)const{
return dis<x.dis;
}
}e[MAXN*MAXN];
struct edge2 //MST邻接表
{
int to,next;
double val;
}e2[MAXN];
void add(int from,int to,double val)
{
e2[len].to=to;
e2[len].val=val;
e2[len].next=head[from];
head[from]=len++;
}
//当访问一个新结点cur时候，考虑所有已经访问过的老结点x，更新f(x,u)=max( f(x,v) ,w(u,v) );
//其中v是u的老结点。
void dfs(int cur,int fa,double dis)
{
for(int i = 0; i < n_len; i++) {
int x = nodes[i];
dp[cur][x] = dp[x][cur] = max(dp[x][fa], dis);
}
nodes[n_len++]=cur;
for(int i=head[cur];i!=-1;i=e2[i].next)
{
int id=e2[i].to;
if(id != fa) dfs(id,cur,e2[i].val);
}
}
//求MST，并且记录
void kruskal()
{
memset(head,-1,sizeof(head));
for(int i=0;i<n;i++)
fa[i]=i;
int &len=e_len;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
e[len].from=i;
e[len].to=j;
e[len++].dis = sqrt( (p[i].y-p[j].y)*(p[i].y-p[j].y)
+(p[i].x-p[j].x)*(p[i].x-p[j].x) );
}
int cnt=0;
mstlen=0;
sort(e,e+len);
for(int i=0;i<len;i++)
{
int x=e[i].from,y=e[i].to;
int root_x=find(x),root_y=find(y);
if(root_x==root_y) continue;
mstlen+=e[i].dis;
fa[root_x]=root_y;
add(x,y,e[i].dis); //建立MST的邻接表
add(y,x,e[i].dis);
if(++cnt > n-1) break;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
len=n_len=e_len=p_len=0;
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].num);
kruskal();
dfs(0,-1,0);
double ans = -1;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++) {
ans = max(ans, (p[i].num+p[j].num) / (mstlen - dp[i][j]));
}
printf("%.2lf\n", ans);
}
return 0;
}