3247. 铁路修复计划

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

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

输入格式

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

第一行是三个整数

接下来 行,每行四个整数 。表示一条城际铁路,连接着 城市, 表示铁路实际修复费用。 表示只能由国外公司修复, 表示由国内公司修复。。输入保证两个城市之间不会存在多条铁路。

输入保证:

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

输出格式

的最大值。输出答案与标准答案相差不超过 即判为正确。

样例

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

271 人解决,351 人已尝试。

403 份提交通过,共有 2457 份提交。

3.0 EMB 奖励。

创建: 2 年,8 月前.

修改: 2 年,4 月前.

最后提交: 1 月,1 周前.

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

题目标签