【題解】\(quake\)
題目大意
我們共有報酬\(f\)元，一條邊有它的價值\(w_i\),有它的建造時間\(t_i\)。要求建一些邊，生成一顆樹。求最大的利潤率。
數據范圍
\(n\le 400\) \(m\le10000\)
\(Solution\)
實際上\(n,m\)出到\(\le 100000\)應該也是沒問題的。
分數形式？考慮數學表示一下
### \(\frac{f-\Sigma c_i}{\Sigma t_i}\le ans\)
### \(f-\Sigma c_i\le ans\Sigma t_i\)
### \(\Sigma(ans\times t_i + c_i) \le f\)
二分就完事了，然后直接克魯斯卡爾。
#include<bits/stdc++.h>#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)
#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)
#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)
#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]
#define midd register int mid=(l+r)>>1
#define TMP template<class ccf>
#define rgt L,R,mid,r,pos<<1|1
#define lef L,R,l,mid,pos<<1
#define all 1,n,1using namespace std;typedef long long ll;typedef long double db;
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Abs(ccf a){return a<0?-a:a;}
TMP inline ccf qr(ccf k){char c=getchar();ccf x=0;int q=1;while(c<48||c>57)q=c==45?-1:q,c=getchar();while(c>=48&&c<=57)x=x*10+c-48,c=getchar();return q==-1?-x:x;
}
//-------------template&IO---------------------
const int maxn=405;
int r[maxn];
int head[maxn];
int cnt;
int n,m;
long double F;
long double mid;
const long double EPS=1e-10;struct S{int fr,to;long double w,t;inline void mk(int FR,int TO,int W,int T){fr=FR;to=TO;w=W;t=T;}inline bool operator <(S a){return t*mid+w<a.t*mid+a.w;}
}data[10001];inline void add(int fr,int to,int w,int t){data[++cnt].mk(fr,to,w,t);
}inline int q(int x){register int t=x,temp,i=x;while(r[t]!=t) t=r[t];while(r[i]!=i){temp=r[i];r[i]=t;i=temp;}return t;
}inline void j(int x,int y){r[q(x)]=q(y);}
inline bool in(int x,int y){return q(x)==q(y);}inline bool chek(){RP(t,1,n) r[t]=t;sort(data+1,data+m+1);long double ret=0;RP(p,1,m)if(!in(data[p].fr,data[p].to))ret+=data[p].t*mid+data[p].w,j(data[p].fr,data[p].to);return ret<=F+EPS||ret+EPS<=F;
}int t1,t2,t3,t4;
int main(){
#ifndef ONLINE_JUDGEfreopen("quake.in","r",stdin);freopen("quake.out","w",stdout);
#endifn=qr(1);m=qr(1);F=qr(1);RP(t,1,m){t1=qr(1);t2=qr(1);t3=qr(1);t4=qr(1);add(t1,t2,t3,t4);}long double l=0,r=2000000001;mid=0;if(!chek()){puts("0.0000\n");return 0;}do{mid=(l+r)/(db)2;if(chek())l=mid;elser=mid;}while(l+EPS<r);printf("%.4Lf",l);return 0;}/*分數形式？考慮數學表示一下### $\frac{f-\Sigma c_i}{\Sigma t_i}\le ans$### $f-\Sigma c_i\le ans\Sigma t_i$### $\Sigma(ans\times t_i + c_i) \le f$二分就完事了*/
