← 返回题目列表

AtCoder · arc026_4

D. 修路工作

中文机器翻译题面 查看原题

問題文

在动感王国里 有 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... ,这是最小值。