【题解】(quake)
题目大意
我们共有报酬(f)元,一条边有它的价值(w_i),有它的建造时间(t_i)。要求建一些边,生成一颗树。求最大的利润率。
数据范围
(nle 400) (mle10000)
(Solution)
实际上(n,m)出到(le 100000)应该也是没问题的。
分数形式?考虑数学表示一下
(frac{f-Sigma c_i}{Sigma t_i}le ans)
(f-Sigma c_ile ansSigma t_i)
(Sigma(ans imes 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,1
using 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_JUDGE
freopen("quake.in","r",stdin);
freopen("quake.out","w",stdout);
#endif
n=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
");
return 0;
}
do{
mid=(l+r)/(db)2;
if(chek())
l=mid;
else
r=mid;
}while(l+EPS<r);
printf("%.4Lf",l);
return 0;
}
/*
分数形式?考虑数学表示一下
### $frac{f-Sigma c_i}{Sigma t_i}le ans$
### $f-Sigma c_ile ansSigma t_i$
### $Sigma(ans imes t_i + c_i) le f$
二分就完事了
*/