[USACO01OPEN] Earthquake

题目描述

一场地震把约翰家的牧场摧毁了，坚强的约翰决心重建家园。约翰已经重建了 $n$ 个牧场，现在他希望能修建一些道路把它们连接起来。研究地形之后，约翰发现可供修建的道路有 $m$ 条。碰巧的是，奶牛们最近也成立一个工程队，专门从事修复道路。而然，奶牛们很有经济头脑，如果无利可图，它们是不会干的。

奶牛们关注的是挣钱速度，即总利润和总施工时间的比值。约翰和奶牛达成了协议，奶牛负责修建道路，将所有牧场连通，而约翰需要支付 $f$ 元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的，不过也有可能一些道路的建造成本之和会超过 $f$。

请帮助奶牛们选择修复哪些道路，才能使单位时间的利润最大？

输入格式

第一行三个整数 $n,m,f$。

第二行到第 $m+1$ 行，第 $i+1$ 行表示第 $i$ 条道路的信息。每行有四个整数 $u_i,v_i,c_i,t_i$，$u_i$ 和 $v_i$ 表示这条道路连接的牧场编号，$c_i$ 表示修建道路的成本，$t_i$ 表示道路修建所需要的时间。

输出格式

第一行，一个保留四位小数的浮点数，表示奶牛们能挣到的最大单位时间利润，如果奶牛们无钱可赚，则输出0.0000。

输入输出样例

输入样例 #1

5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1

输出样例 #1

1.0625

说明/提示

样例输入输出 1 解释

奶牛们可以选择连通最后四条道路，则总时间为 $16$，总成本为 $83$，所以单位利润为 $\dfrac{17}{16}=1.0625$。

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \leq n \leq 400$，$1 \leq m \leq 10000$，$1 \leq f \leq 2 \times 10^9$。
• $1 \leq u_i,v_i \leq n$，$1 \leq c_i,t_i \leq 2 \times 10^9$。