3247. 铁路修复计划

单点时限: 2.0 sec

内存限制: 256 MB

在 A 国有很多城际铁路。这些铁路都连接两个城市(城市从 $1$ 到 $n$ 编号),可以双向通行,使得任意两个城市之间都由铁路网联系起来。

不过在一次星球大战之后,所有的铁路都经历了不同程度的损伤以至于无法通行了。由于经费紧缺,A 国政府不愿意再出资造新的铁路。对于原有的城际铁路,根据铁路的实际情况,有以下两种处理办法:

  1. 使用国内技术进行修复:主要针对损坏情况不是很严重的铁路。国内公司会对铁路状况进行评估,然后如实开出铁路修复的费用。
  2. 使用国外技术进行修复:主要针对损坏情况严重的铁路。国外公司也会对铁路情况进行评估,然后按照铁路实际修复费用的 $k$ 倍来收费(其中 $k$ 是一个由国外公司决定的实数,不管怎么说,优惠是不可能的,所以 $k \geq 1$)。

A国政府修复铁路的总预算是 $M$,目标是要让任意两个城市之间都能通过铁路联系起来。在预算不够且能够完成目标的条件下,显然没必要修复每一条铁路。

国外公司通过不知什么途径了解到了 A 国政府的总预算 $M$,他们现在要把 $k$ 定下来,并且希望 $k$ 尽可能得大。但 $k$ 又不能太大,不然,如果 A 国政府发现无法完成任务的话,整个订单都会泡汤。

输入格式

测试数据包含不超过 30 个测试文件。每个测试文件是单个测试点。

第一行是三个整数 $n, m, M$ $(2 \leq n \leq 10^5, n-1 \leq m \leq \min {10^5, \frac{n(n-1)}{2} }, 1 \leq M \leq 10^{15})$。

接下来 $m$ 行,每行四个整数 $u_i, v_i, t_i, f_i$。表示一条城际铁路,连接着 $u_i$ 和 $v_i$ 城市,$t_i$ 表示铁路实际修复费用。$f_i=1$ 表示只能由国外公司修复,$f_i=0$ 表示由国内公司修复。$(1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq t_i \leq 10^6, f_i \in {0, 1})$。输入保证两个城市之间不会存在多条铁路。

输入保证:

  • 在国外公司不乱收费 $(k=1)$ 的情况下,使用预算能完成要求。
  • 完全不使用国外技术,只使用国内技术,是不能完成目标的。

输出格式

求 $k$ 的最大值。输出答案与标准答案相差不超过 $10^{-6}$ 即判为正确。

样例

Input
3 3 9
1 2 1 1
1 3 2 0
2 3 1 1
Output
7.000000
Input
3 3 9
1 2 1 1
1 3 2 1
2 3 2 1
Output
3.000000

293 人解决,383 人已尝试。

432 份提交通过,共有 2667 份提交。

2.9 EMB 奖励。

创建: 7 年,4 月前.

修改: 7 年,1 月前.

最后提交: 6 月,2 周前.

来源: 2017 华东师范大学网赛

题目标签