原题大意

在 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 即判为正确。

算法分析

二分 k，然后每次对边重新赋值排序后，就是经典的 MST 问题了。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100005;
int n, m;
ll M;
struct Edge{
    int u, v;
    double t;
    int cost;
    int f;
    bool friend operator < (Edge a, Edge b){
        return a.t < b.t;
    }
}edge[maxn];
int p[maxn];
int find(int  x){return p[x] == x? x : p[x] = find(p[x]);}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> M;
    for(int i = 0; i < m; i++){
        cin >> edge[i].u >> edge[i].v >> edge[i].cost>> edge[i].f;
    }
    double l = 1.0, r = M; 
    double mid;
    while(r-l > 1e-7){
        mid = (l+r)/2.0;
        for(int i = 0; i < m; i++){
            if(edge[i].f == 1) edge[i].t = mid * edge[i].cost;
            else edge[i].t = edge[i].cost;
        }
        sort(edge, edge+m);
        double ans = 0.0;
        for(int i = 0; i <= n; i++) p[i] = i;
            for(int i = 0; i < m; i++){
                int x = find(edge[i].u);
                int y = find(edge[i].v);
                if(x!=y){ans += edge[i].t; p[x] = y;}
            }
        if(ans < M) l=mid;
        else r=mid;
    }
    printf("%.6lf\n", l);

    return 0;
}