問題文
在动感王国里 有 N 个村庄, 它们的编号最大为0 从 N-1 。那些村庄 M 我们通过书籍的路径联系在一起。 “连通”指的是一种状态,在这种状态下,你可以沿着多条路径从任何村庄到达任何其他村庄。有一天,一场大灾难导致所有道路被毁,村庄之间无法通行。高桥国王将要求您修复道路并建立一个充满活力的王国。 N 我被要求做将几个村庄连接在一起的工作。
您首先估算修复每条道路所需的成本和时间。然后,我决定在适当选择维修路径时计算“最低盈利小时工资”的最小值。 “最低盈利小时工资”是指“修路所需的总时间”ד小时工资”等于“修路所需的总成本”时的“小时工资”的值。
请注意,不需要修复所有道路,并且可以修复不需要连接村庄的道路。
入力
输入将以以下格式从标准输入给出。
N M A_1 B_1 C_1 T_1 A_2 B_2 C_2 T_2 : A_M B_M C_M T_M
-
1 行包含一个代表村庄数量的整数。 N (2 ≦ N ≦ 10^4) 和代表道路数量的整数 M (1 ≦ M ≦ 10^4) 用空格分隔。
-
继续 M 行提供道路信息。其中 i 在线 4 整数 A_i (0 ≦ A_i ≦ N-1), B_i (0 ≦ B_i ≦ N-1), C_i (1 ≦ C_i ≦ 10^6), T_i (1 ≦ T_i ≦ 10^6) 是用空格隔开的,是村庄 A_i 和村庄 有一条路连接 B_i ,修这条路需要花钱。 C_i,时间 T_i 这意味着需要一些时间。
此外,可以假设关于道路信息以下条件成立。
- 全部 关于 i , 关于A_i \neq B_i
- 全部 关于 i, j (i \neq j) ,A_i \neq A_j 或 B_i \neq B_j”和“A_i \neq B_j 或 B_i \neq A_j」
部分点
针对此问题设置了部分分数。 如果所有满足
- M ≦ 16 的测试用例都得到正确回答, 给出 20 点。
出力
“最低盈利小时工资”的最小值 1 行输出。
输出有绝对误差 10^{-2} 或更少是可以接受的。
请在输出末尾添加换行符。
入力例1
3 2 0 1 5 3 1 2 5 2
出力例1
2
在这种情况下,必须修复所有道路以连接城镇。修复所有道路的总成本为 总时间为 10 总时间是 5 ,所以有利可图的最低小时工资是 2 。
错误是 最多允许 10^{-2} ,因此 输出类似2.01 呀 1.99 的内容也是正确的。
入力例2
3 3 0 1 1 1 1 2 3 1 2 0 2 1
出力例2
1.500
在这种情况下,1 第二路 3 修第二条路时,“最低盈利时薪”为 1.5 ,这是最小值。
入力例3
4 4 0 1 1 1 1 2 1 1 2 0 1 1 0 3 5 3
出力例3
1.3333333
在这种情况下,修复所有道路时的“最低盈利每小时费率”为 我有一个 1.333... ,这是最小值。