?

题意：

有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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         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
        
         mmax){ mmax=peo[i]; root=i; } } int cnt = 0; for(int i=0;i
         
          
?
          
?
          
?
          
?