2018.09.12 earthquake(最適比率生成ツリー)

説明
地震は農夫ジョンのすべての農場とすべての農場を結ぶ道を破壊した.意志の強い人として、彼はすべての農場を再建することにした.すべてのN(1<=N<=400)農場を再建する前に、まずすべての農場を道路で接続しなければならない.すなわち、任意の2つの農場の間に少なくとも1つの通路が必要である.地図を研究した後、農夫のジョンはM(1<=M<=10000)の双方向の道路が短い時間で建設できると結論した.ジョンは資金が限られているので、できるだけ安い方法で工事を完成したいと思っています.たまたま、農場の乳牛たちは地震で破壊された農場の道路を再改造する工事会社を設立し、ジョンは道路再建の仕事を乳牛たちに任せることにした.これらの牛も鋭いビジネス感覚を持っていて、工事から最大の利益を得ることを望んでいます.ジョンと乳牛たちは協議を経て、ジョンはF(1<=F<=20000000)元を出して乳牛たちに道路再建に使い、乳牛たちにすべての農場を道路でつなぐように要求した.つまり、任意の2つの農場の間に少なくとも1つの通路が必要だ.乳牛たちは地図から各道路を建設するコストc(1<=c<=20000000)と使用時間t(1<=t<=20000000)を推定し、1対の農場の間に1つ以上の道路を再建することができ、与えられたテストデータに対してすべての農場を接続することができる.今、乳牛たちはあなたを見つけて、農場の道路を再建して乳牛たちに最大の利益率を得るプログラムを作るように要求しています.つまり、残りの経費とかかる時間の比(お金を稼ぐスピード)を最大にします.
入力
入力ファイルには、m+1行、第1行の3つの整数N,M,F、第2行から第M+1行が含まれ、各行には、i,j,c,tの4つのスペースで区切られた整数が含まれています.
しゅつりょく
残りの経費とかかる時間の比を示す実数を含み、4桁の小数を残す.既存の経費ですべての道路を接続できない場合は、0.0000を出力します.
サンプル入力
5 5 100 1 2 20 5 1 3 20 5 1 4 20 5 1 5 20 5 2 3 23 1
サンプル出力
1.0625
ヒント
サンプルは乳牛たちが最後の4つの道路を建設することができることを説明して、このように費やした経費は83で、利益は17で、使った時間は16で、だから、彼らは16単位の時間の中で17元利益を得て、だから比値は(100-83)/16=1.0625です.
タブ
USACO_2001_open_GREEN
単純な最適比率生成ツリー.F−Σc[i]Σt[i]F−Σc[i]Σt[i]の最大値が要求される.変形はF−Σ(c[i]+k∗t[i])>=0 F−Σ(c[i]+k∗t[i])>=0という簡単な01分数計画+最小生成ツリーである.コード:

#include
#define N 405
#define M 10005
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int n,m,first[N],F,fa[N];
struct Node{int u,v,c,t;double w;}e[M];
inline bool cmp(Node a,Node b){return a.w>b.w;}
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
inline bool kruskal(double mid){
    double ret=0.0;
    int cnt=0;
    for(int i=1;i<=m;++i)e[i].w=-1.0*e[i].t*mid-e[i].c*1.0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        if(cnt==n-1)break;
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx!=fy)fa[fx]=fy,ret+=e[i].w;
    }
    return ret+F>=0;
}
int main(){
    n=read(),m=read(),F=read();
    for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].c=read(),e[i].t=read();
    double l=0.0,r=60000;
    while(r-l>1e-7){
        double mid=(l+r)/2;
        if(kruskal(mid))l=mid;
        else r=mid;
    }
    printf("%.4lf",l);
    return 0;
}