題意:
有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