AT_arc026_4 [ARC026D] 道を直すお仕事

[problemUrl]: https://atcoder.jp/contests/arc026/tasks/arc026_4 ダイナミック王国には $ 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 $」

「採算がとれる最低限の時給」の最小値を $ 1 $ 行に出力せよ。 出力は絶対誤差が $ 10^{-2} $ 以下であれば許容される。 なお、出力の末尾には改行をいれること。

### 部分点 この問題には部分点が設定されている。 - $ M\ ≦\ 16 $ を満たすテストケースすべてに正解した場合は $ 20 $ 点が与えられる。 ### Sample Explanation 1 このケースでは、町をひと繋がりにするためには全ての道を修理しなければなりません。全ての道を修理するためにかかる費用の合計が $ 10 $ で時間の合計が $ 5 $ であるため、採算がとれる最低限の時給は $ 2 $ となります。 誤差は $ 10^{-2} $ まで許容されるため、$ 2.01 $ や $ 1.99 $ などと出力しても正解となります。 ### Sample Explanation 2 このケースでは、$ 1 $ つ目の道と $ 3 $ つ目の道を修理するときに「採算がとれる最低限の時給」が $ 1.5 $ となり、最小となります。 ### Sample Explanation 3 このケースでは、全ての道を修理するときに「採算がとれる最低限の時給」が $ 1.333... $ となり、最小となります。