题目链接：传送门

题意：

有n坐城市，知道每坐城市的坐标和人口。如今要在全部城市之间修路，保证每一个城市都能相连，而且保证A/B 最大。全部路径的花费和最小，A是某条路i两端城市人口的和，B表示除路i以外全部路的花费的和（路径i的花费为0）.

分析：

先求一棵最小生成树，然后枚举每一条最小生成树上的边，删掉后变成两个生成树。然后找两个集合中点权最大的两

个连接起来。这两个点中必定有权值最大的那个点。所以直接从权值最大的点開始dfs。

　　为了使A/B的值最大，则A尽可能大，B尽可能小。所以B中的边一定是MST上去掉一条边后的剩余全部边。首先用O(N^2)算出

　　MST，然后依次枚举。删去MST上的每一条边。MST变成两棵树T1和T2，然后在剩余的边（即不在MST上的边），以及这条删

　　去的边中找到该边的两点的权值和最大以及可以连接T1和T2的边。A=删去边后的替换边的两点的权值和，B=删去该边后的MST

　　的值。求A/B最大。

则A尽可能大，A各自是T1和T2中最大的两个点，则全部点中权值最大的点一定在A中。由此在MST上从权值

　　最大的点作为root。開始dfs。递归求出子树中的每一个最大的点以及求出A/B的比值，求出最大。

分析转载自：传送门

我的理解。首先非常明显我们是须要求出最小生成树的，然后我们能够枚举边(u,v)中的边，非常明显枚举的边都会

与原来MST中的边形成一个环，由于这个边不在MST中，那么这个边的权值一定是大于MST中连接U,V的边的，因此

我们在这个环里去掉的应该是权值最大的边。

代码例如以下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

const int maxn = 1e3+10;

const int inf = 1e9+10;

struct point{

    int x,y;

}a[maxn];

int head[maxn],par[maxn],peo[maxn];

bool vis[maxn];

int ip,mmax;

double ans ,mst;

struct tree{

    int u,v;

    double w;

    tree(){}

    tree(int _u,int _v,double _w):u(_u),v(_v),w(_w){}

    bool operator < (const struct tree &tmp)const{

        return w<tmp.w;

    }

}mp[maxn*maxn];

struct nod{

    int to,next;

    double w;

}edge[maxn*2];

double calu(point a,point b){

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

void add(int u,int v,double w){

    edge[ip].to=v;

    edge[ip].w=w;

    edge[ip].next=head[u];

    head[u]=ip++;

}

int find_par(int x){

    if(x!=par[x]) return par[x]=find_par(par[x]);

    return par[x];

}

bool Union(int x,int y){

    x=find_par(x);

    y=find_par(y);

    if(x!=y){

        par[x]=y;

        return true;

    }

    return false;

}

void init(){

    for(int i=0;i<maxn;i++) par[i]=i;

    ip=mmax=0;

    ans=mst=0;

    memset(head,-1,sizeof(head));

    memset(vis,0,sizeof(vis));

}

int dfs(int root){

    vis[root]=1;

    int peo_max=peo[root];

    for(int i=head[root];i!=-1;i=edge[i].next){

        int v=edge[i].to;

        if(!vis[v]){

            int tmp = dfs(v);

            peo_max=max(peo_max,tmp);

            ans=max(ans,(tmp+mmax)/(mst-edge[i].w));

        }

    }

    return peo_max;

}

int main(){

    int t,n,root;

    scanf("%d",&t);

    while(t--){

        init();

        scanf("%d",&n);

        for(int i=0;i<n;i++){

            scanf("%d%d%d",&a[i].x,&a[i].y,&peo[i]);

            if(peo[i]>mmax){

                mmax=peo[i];

                root=i;

            }

        }

        int cnt = 0;

        for(int i=0;i<n;i++){

            for(int j=i+1;j<n;j++){

                mp[cnt++]=tree(i,j,calu(a[i],a[j]));

            }

        }

        sort(mp,mp+cnt);

        for(int i=0;i<cnt;i++){

            if(Union(mp[i].u,mp[i].v)){

                mst+=mp[i].w;

                add(mp[i].u,mp[i].v,mp[i].w);

                add(mp[i].v,mp[i].u,mp[i].w);

            }

        }

        dfs(root);

        printf("%.2lf\n",ans);

    }

    return 0;

}