HDU 4081 Qin Shi Huang's National Road System(最小生成樹/次小生成樹）

HDU 4081 Qin Shi Huang's National Road System(最小生成樹/次小生成樹）

題意：

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