ECNU 3247

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

input

output

7.000000

input

output

3.000000

Source

2017 华东师范大学网赛

这题原本跟队友想了很久都不知道怎么做（咸鱼如我，一度表示这题大概超出我们的能力范围了……），然后shiyang和trader大佬跟我们说：

二分k值，对每个k值进行kruskal，判断最小生成树的每条边的weight的sum是不是小与等于M；

综合运用二分、kruskal、并查集的题目，总的来说还是一道不错的题，做完有种很爽的感觉~

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define MAX 100000+5
 4 #define EPS 1e-7
 5 using namespace std;
 6 struct Road{
 7     int type;
 8     int u,v,cost;
 9     double w;
10 }road[MAX];
11 int n,m;
12 double M;
13 
14 int par[MAX];
15 void init(){for(int i=1;i<=n;i++) par[i]=i;}
16 int find(int x){return( par[x]==x ? x : par[x]=find(par[x]) );} 
17 void unite(int x,int y)
18 {  
19     x=find(x),y=find(y);  
20     if(x == y) return;
21     par[y]=x;
22 }
23 bool kruskal()
24 {
25     int cnt=0;
26     double sum=0.0;
27     init();
28     for(int i=1;i<=m;i++)
29     {
30         int x=find(road[i].u) , y=find(road[i].v);
31         if(x!=y)
32         {
33             unite(x,y);
34             sum+=road[i].w;
35             if((++cnt)==n-1) break;
36         }
37     }
38     if(sum>M) return 0;
39     return 1;
40 }
41 
42 bool cmp(Road a,Road b){return a.w<b.w;}
43 bool check(double k)
44 {
45     for(int i=1;i<=m;i++)
46     {
47         if(road[i].type==1) road[i].w=k*road[i].cost;
48         else road[i].w=1.0*road[i].cost;
49     }
50     sort(road+1,road+m+1,cmp);
51     return kruskal();
52 }
53 int main()
54 {
55     scanf("%d%d%lf",&n,&m,&M);
56     for(int i=1;i<=m;i++) scanf("%d%d%d%d",&road[i].u,&road[i].v,&road[i].cost,&road[i].type);
57     double st=0.0,ed=1e15+1,mid;
58     while(ed-st>EPS)
59     {
60         mid=st+(ed-st)/2.0;
61         if(check(mid)) st=mid;
62         else ed=mid;
63     }
64     printf("%.6lf
",st);
65 }