#P4951. [USACO01OPEN] Earthquake
[USACO01OPEN] Earthquake
题目描述
一场地震把约翰家的牧场摧毁了, 坚强的约翰决心重建家园。 约翰已经重建了 个牧场,现在他希望能修建一些道路把它们连接起来。研究地形之后,约翰发现可供修建的道路有 条。碰巧的是,奶牛们最近也成立一个工程队,专门从事修复道路。而然,奶牛们很有经济头脑,如果无利可图,它们是不会干的。
奶牛们关注的是挣钱速度,即总利润和总施工时间的比值。约翰和奶牛达成了协议,奶牛负责修建道路,将所有牧场连通,而约翰需要支付 元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的,不过也有可能一些道路的建造成本之和会超过 。
请帮助奶牛们选择修复哪些道路,才能使单位时间的利润最大?
输入格式
第一行三个整数 。
第二行到第 行,第 行表示第 条道路的信息。每行有四个整数 , 和 表示这条道路连接的牧场编号, 表示修建道路的成本, 表示道路修建所需要的时间。
输出格式
第一行,一个保留四位小数的浮点数,表示奶牛们能挣到的最大单位时间利润,如果奶牛们无钱可赚,则输出0.0000
。
5 5 100
1 2 20 5
1 3 20 5
1 4 20 5
1 5 20 5
2 3 23 1
1.0625
提示
样例输入输出 1 解释
奶牛们可以选择连通最后四条道路,则总时间为 ,总成本为 ,所以单位利润为 。
数据规模与约定
对于 的数据,保证
- ,,。
- ,。