[USACO]地震 （二分答案+最優比率生成樹詳解）

題面：[USACO 2001 OPEN]地震

題目描述：

一場地震把約翰家的牧場摧毀了， 堅強的約翰決心重建家園。 約翰已經重建了N個牧場，現在他希望能修建一些道路把它們連接起來。研究地形之后，約翰發現可供修建的道路有M條。碰巧的是，奶牛們最近也成立一個工程隊，專門從事修復道路。而然，奶牛們很有經濟頭腦，如果無利可圖，它們是不會干的。
奶牛們關注的是掙錢速度，即總利潤和總施工時間的比值。約翰和奶牛達成了協議，奶牛負責修建道路，將所有牧場連通，而約翰需要支付F元。每條道路都有自己的施工時間和建造成本。連接兩個相同的牧場的道路可能有多條。保證所有的牧場必定是可連通的，不過也有可能一些道路的建造成本之和會超過F。

請幫助奶牛們選擇修復哪些道路，才能使單位時間的利潤最大？

輸入格式：

第一行：三個整數： N，M和F，\(1 ≤ N ≤ 400\)，\(1 ≤ M ≤ 10000\)，\(1 ≤ F ≤ 2 × 10^9\)
第二行到\(M + 1\)行：第\(i + 1\)行表示第i條道路的信息，有四個整數：\(U_i\) ，\(V_i\) ，\(C_i\) 和\(T_i\) ，\(U_i\) 和\(V_i\) 表示這條道路連接的牧場編號，Ci表示道路修建的成本，Ti表示道路修建所需要的時間，\(1 ≤ U_i ≤ N\)，\(1 ≤ V_i ≤ N\)，$1 ≤ C_i ≤ 2 × 10^9 $，\(1 ≤ T_i ≤ 2 × 10^9\)

輸出格式：

第一行：一個保留四位小數的浮點數，表示奶牛們能掙到的最大單位時間利潤，如果奶牛們無錢可賺，則輸出0.0000

輸入樣例#1：

5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1

輸出樣例#1：

1.0625

說明:

（奶牛們可以選擇連通最后四條道路，則總時間為 16，總成本為 83，所以單位利潤為17/16 = 1.0625）

\(solution:\)

這題其實牽扯到了一種普遍的二分答案的方法，與我等下會講的HNOI2009 最小圈 一樣有許多的共同點。因為這些題要求我們輸出的ans都是針對權值總和不斷計算而來的。本題就是個經典例題（二分答案求最優比率生成樹），因為我們可以直接通過題意看出它要求我們輸出的最終答案實際上就是：

$ans= \frac{F-\sum{v_i} \quad (i\in S)}{\sum{t_i}\quad (i\in S)} $

（其中S為我們最終所選擇的最優生成樹的邊權的集合）我們將這個式子轉換一下，可以得到：

\(F=ans*\sum{t_i}+\sum{v_i}\)

\(F=\sum{ans*t_i+v_i}\quad _{(i\in S)}\)

注：這一點我們一定要清楚：此時等式右邊就是生成樹（只不過；樹邊權變成了\(ans*t_i+v_i\)）

上述式子中我們的ans就是我們最終要輸出的最優比率，這個ans是我們可以二分得到的！因為答案具有單調性，當然這個需要我們進一步證明：首先，因為ans是最優比率，那么我們可以知道，對于圖上的任意一個生成樹的邊的集合K，一定有：$\frac{F-\sum{v_i} \quad (i\in K)}{\sum{t_i}\quad (i\in K)}\leq ans $ （根據上述方式轉化得：\(F\leq \sum{ans*t_i+v_i}\quad {(i\in K)}\)）只有當我們的集合K取到最優的生成樹時也就是K=S的時候，這個式子才會是等式！然后我們來證明二分的正確性：當我們二分求ans的時候，對于我們當前的比率x，一定有這三種情況：

\(1.\) \(x>ans\) ：

當我們比率為ans時：\(F\leq \sum{ans*t_i+v_i}\quad {(i\in K )}\)

現在我們的比率x比ans還大！那我們的肯定有：\(F< \sum{x*t_i+v_i}\quad {(i\in K)}\)

\(2.\) \(x=ans\) ：

我已經說過了：\(F\leq\sum{ans*t_i+v_i}\quad {(i\in K)}\)

\(3.\) \(x<ans\) ：

這個時候我們發現我們不能確認\(F\) 和 \(\sum{ans*t_i+v_i}\quad {(i\in K)}\) 的大小關系了！因為我們的K是任意生成樹的邊的集合，此時我們小于等于大于都有可能，但也正是如此，我們可以證明一定存在一個邊的集合滿足\(F>\sum{x*t_i+v_i}\quad {(i\in S)}\)因為就拿我們ans情況下的最優邊集S，因為 \(F=\sum{ans*t_i+v_i}\quad {(i\in S)}\) 此時我們的\(x<ans\) 所以\(F>\sum{x*t_i+v_i}\quad {(i\in S)}\)

如何二分（為什么用最小生成樹）：

那我們證明了上面這個東西有什么用呢？根據上述三個關系的特性（就是那三個不等式），我們發現當我們將x帶進去后，只要求得最小的 \(\sum{ans*t_i+v_i}\quad {(i\in K)}\) 我們就可以直接判斷出x和ans的關系了！

我們將最小的\(\sum{ans*t_i+v_i}\quad {(i\in K)}\) 看做min

1. 若\(F<min\)，則必有\(F< \sum{x*t_i+v_i}\quad {(i\in K)}\) 這不就是第一種情況嗎？x必然大于ans

2. 若\(F=min\)，則必有\(F \leq \sum{x*t_i+v_i}\quad {(i\in K)}\) 這不就是第一種情況嗎？x必然等于ans

3. 若\(F>min\)，則x必然不大于也不等于ans，那不就是小于ans嗎？（證過了若x<ans，則必存在一個K\(F>\sum{x*t_i+v_i}\quad {(i\in K)}\)）

那我們如何求最小的\(\sum{x*t_i+v_i}\quad {(i\in K)}\) 呢？ 這就是求最小生成樹嘛（只不過；樹邊權變成了\(ans*t_i+v_i\)，我們每一次都重新排個序就行了）！

總復雜度：\(O(m *logm*log(r-l+1))\)

\(code:\)

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>#define ll long long
#define db double
#define rg register intusing namespace std;const db cha=1e-9;struct su{int x,y,v,t;db k;
}a[10005];int n,m,f;
int s[405];inline int qr(){char ch;while((ch=getchar())<'0'||ch>'9');int res=ch^48;while((ch=getchar())>='0'&&ch<='9')res=res*10+(ch^48);return res;
}inline bool cmp(su x,su y){return x.k<y.k;}inline int get(int x){if(s[x]==x)return x;return s[x]=get(s[x]);
}inline bool check(db x){db res=0;for(rg i=1;i<=n;++i)s[i]=i;//并查集for(rg i=1;i<=m;++i)a[i].k=x*a[i].t+(db)a[i].v;//更新邊權sort(a+1,a+m+1,cmp);//kruskal求最小生成樹for(rg i=1;i<=m;++i)if(get(a[i].x)!=get(a[i].y))res+=a[i].k,s[get(a[i].x)]=get(a[i].y);//求新邊權的總和return f>res?0:1;
}int main(){freopen("quake.in","r",stdin);freopen("quake.out","w",stdout);n=qr(),m=qr(),f=qr();for(rg i=1;i<=m;++i)a[i]=su{qr(),qr(),qr(),qr()};if(check(0))puts("0.0000"),exit(0);//特判db l=0,r=1e14,mid;while(r-l>cha){//二分答案mid=(l+r)/2;if(check(mid))r=mid-cha;else l=mid+cha;}printf("%.4lf",l);return 0;
}