LA 5713 秦始皇修路

题意：

秦朝有n个城市，需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路，不花钱，也不用劳动力，但只能修一条路，因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短（这样可以节省劳动力），还希望法术连接的两个城市的人口之和A尽量大，因此下令寻找一个使得A/B最大的方案。你的任务是找到这个方案。

任意两个城市之间都可以修路，长度为两个城市之间的欧几里德距离。

思路：

先计算出最小生成树，之后用法术修的路肯定在最小生成树当中，那么之后我们就可以枚举边u-v。

当然，需要预处理，像最小生成树一样，计算出u和v之间唯一路径上的最大权maxcost[u][v]。

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 const int maxn=+;

 struct node

 {

     int u,v;

     double dist;

     bool operator < (const node& rhs) const

     {

         return dist<rhs.dist;

     }

 }edge[maxn*maxn];

 int n;

 int cnt;

 int p[maxn];

 int x[maxn],y[maxn];

 int num[maxn];

 vector<int> g[maxn];   //存储最小生成树中结点u的邻接结点

 vector<double> c[maxn];  //c[u][i]表示结点u和和结点g[u][i]之间的边权

 double maxcost[maxn][maxn];  //u，v两点之间的最大边权

 vector<int> nodes;

 int find(int x)

 {

     return x==p[x]?x:p[x]=find(p[x]);

 }

 double MST()

 {

     sort(edge,edge+cnt);

     int tot_edge=;

     double tot_q=;

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

     {

         int x=edge[i].u, y=edge[i].v;

         int u=find(x), v=find(y);

         if(u!=v)

         {

             p[u]=v;

             g[x].push_back(y); c[x].push_back(edge[i].dist);

             g[y].push_back(x); c[y].push_back(edge[i].dist);

             tot_q+=edge[i].dist;

             if(++tot_edge==n-)  break;

         }

     }

     return tot_q;

 }

 void dfs(int u,int fa,double cost)  //无根树转有根树，计算出u，v两点之间路径的最大边权

 {

     for(int i=;i<nodes.size();i++)

     {

         int x=nodes[i];

         maxcost[x][u]=maxcost[u][x]=max(maxcost[x][fa],cost);   //更新之前的结点与新加入的结点之前的最大边权

     }

     nodes.push_back(u);

     for(int i=;i<g[u].size();i++)

     {

         int v=g[u][i];

         if(v!=fa) dfs(v,u,c[u][i]);

     }

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         cnt=;

         scanf("%d",&n);

         for(int i=;i<n;i++)  {p[i]=i; g[i].clear(); c[i].clear();}

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

         {

             scanf("%d%d%d",&x[i],&y[i],&num[i]);

             for(int j=;j<i;j++)

             {

                 edge[cnt].u=j;

                 edge[cnt].v=i;

                 edge[cnt].dist=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

                 cnt++;

             }

         }

         double tot=MST();

         memset(maxcost,,sizeof(maxcost));

         nodes.clear();

         dfs(,-,);

         double ans=-;

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

         {

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

             {

                 ans=max(ans,(num[i]+num[j])/(tot-maxcost[i][j]));

             }

         }

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

     }

     return ;

 }