Time limit per test: 2.0 seconds
Time limit all tests: 15.0 seconds
Memory limit: 256 megabytes
在 A 国有很多城际铁路。这些铁路都连接两个城市（城市从 1 到 n 编号），可以双向通行，使得任意两个城市之间都由铁路网联系起来。
不过在一次星球大战之后，所有的铁路都经历了不同程度的损伤以至于无法通行了。由于经费紧缺，A 国政府不愿意再出资造新的铁路。对于原有的城际铁路，根据铁路的实际情况，有以下两种处理办法：
- 使用国内技术进行修复：主要针对损坏情况不是很严重的铁路。国内公司会对铁路状况进行评估，然后如实开出铁路修复的费用。
- 使用国外技术进行修复：主要针对损坏情况严重的铁路。国外公司也会对铁路情况进行评估，然后按照铁路实际修复费用的 k 倍来收费（其中 k 是一个由国外公司决定的实数，不管怎么说，优惠是不可能的，所以 k≥1）。
A国政府修复铁路的总预算是 M，目标是要让任意两个城市之间都能通过铁路联系起来。在预算不够且能够完成目标的条件下，显然没必要修复每一条铁路。
国外公司通过不知什么途径了解到了 A 国政府的总预算 M，他们现在要把 k 定下来，并且希望 k 尽可能得大。但 k又不能太大，不然，如果 A 国政府发现无法完成任务的话，整个订单都会泡汤。
Input
测试数据包含不超过 30 个测试文件。每个测试文件是单个测试点。
第一行是三个整数 n,m,M (2≤n≤105,n−1≤m≤min{105,n(n−1)2},1≤M≤1015)。
接下来 m 行，每行四个整数 ui,vi,ti,fi。表示一条城际铁路，连接着 ui 和 vi 城市，ti 表示铁路实际修复费用。fi=1 表示只能由国外公司修复，fi=0 表示由国内公司修复。(1≤ui,vi≤n,ui≠vi,1≤ti≤106,fi∈{0,1})。输入保证两个城市之间不会存在多条铁路。
输入保证：
- 在国外公司不乱收费 (k=1) 的情况下，使用预算能完成要求。
- 完全不使用国外技术，只使用国内技术，是不能完成目标的。
Output
求 k 的最大值。输出答案与标准答案相差不超过 10−6 即判为正确。
Examples
3 3 9
1 2 1 1
1 3 2 0
2 3 1 1
7.000000
3 3 9
1 2 1 1
1 3 2 1
2 3 2 1
3.000000
Source
2017 华东师范大学网赛
这题原本跟队友想了很久都不知道怎么做（咸鱼如我，一度表示这题大概超出我们的能力范围了……），然后shiyang和trader大佬跟我们说：
二分k值，对每个k值进行kruskal，判断最小生成树的每条边的weight的sum是不是小与等于M；
综合运用二分、kruskal、并查集的题目，总的来说还是一道不错的题，做完有种很爽的感觉~
#include<cstdio>
#include<algorithm>
#define MAX 100000+5
#define EPS 1e-7
using namespace std;
struct Road{
int type;
int u,v,cost;
double w;
}road[MAX];
int n,m;
double M; int par[MAX];
void init(){for(int i=;i<=n;i++) par[i]=i;}
int find(int x){return( par[x]==x ? x : par[x]=find(par[x]) );}
void unite(int x,int y)
{
x=find(x),y=find(y);
if(x == y) return;
par[y]=x;
}
bool kruskal()
{
int cnt=;
double sum=0.0;
init();
for(int i=;i<=m;i++)
{
int x=find(road[i].u) , y=find(road[i].v);
if(x!=y)
{
unite(x,y);
sum+=road[i].w;
if((++cnt)==n-) break;
}
}
if(sum>M) return ;
return ;
} bool cmp(Road a,Road b){return a.w<b.w;}
bool check(double k)
{
for(int i=;i<=m;i++)
{
if(road[i].type==) road[i].w=k*road[i].cost;
else road[i].w=1.0*road[i].cost;
}
sort(road+,road+m+,cmp);
return kruskal();
}
int main()
{
scanf("%d%d%lf",&n,&m,&M);
for(int i=;i<=m;i++) scanf("%d%d%d%d",&road[i].u,&road[i].v,&road[i].cost,&road[i].type);
double st=0.0,ed=1e15+,mid;
while(ed-st>EPS)
{
mid=st+(ed-st)/2.0;
if(check(mid)) st=mid;
else ed=mid;
}
printf("%.6lf\n",st);
}