TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

37.5% (9/24)

Tags

Description

近年來,北捷可說是越來越發達,除了大家熟知萬大線,三環三線的工程也正如火如荼的進行中
然而這引發了許多南部人的抗議
"為什麼北部人捷運那麼多條線!!"
"我們也要蓋捷運!!"
這令市長感到為難,於是找了北部那些設計捷運路線的人員來幫他處理這個問題,而你也是其中一個
在你設計路線的時候,發現每個站之間有著非常多不同的連結方式
更深入研究之後,你整理出一些結論
1.每條路線建造的花費$y$各有不同
2.每條路線建造時,會讓當地居民的滿意指數$x$也不相同
3.若把所有的路線都建好,則會任意站間都有辦法到達彼此
在跟你的同夥討論完後,你們決定找出一個路線組合,使得任一一站都可以透過轉乘或直接到達所有其他的站
(為了省錢,你們不希望路線圖中有環出現),使得路線的$\frac{\sum{y}}{\sum{x}} $可以最小

Input Format

第一行有兩個正整數$ 1 \le N \le M \le 2 \times 10^ 5 $,分別代表共有幾個站與幾個可行路線
接下來的$M$行有四個整數$u_i, v_i, x_i, y_i (1 \leq u_i, v_i \leq N, 1 \leq x_i, y_i \leq 10^ 9)$
代表從點$u_i$到點$v_i$中間有連通的路線,而$x,y$分別代表居民的滿意指數與建造花費

Output Format

輸出一個數代表比率最小可以為多少
若絕對或相對誤差在$10^ {-6}$內,則會視為正確
(也就是說若您的答案為x,而正確答案為y,則$ \frac{|x-y|}{\max(1, |y|)} < 10^ {-6} $會視為正確)

Sample Input

9 10
2 1 1 6
3 2 1 1
4 2 5 7
5 4 4 9
6 2 4 1
7 3 5 4
8 2 8 8
9 2 9 2
8 7 2 2
1 9 3 1

Sample Output

0.818181818181818

Hints

子任務(測資)額外限制分數
1(0~9)$1 \le N \leq M \le 20 $10
2(10~19)$ x_i = 1 $20
3(20~29)無額外限制70

Problem Source

Problem Set By oToToT
Description By Pooh

Subtasks

For Testdata: 0 ~ 9, Score: 10
For Testdata: 10 ~ 19, Score: 20
For Testdata: 20 ~ 29, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536
10 2000 65536 65536
11 2000 65536 65536
12 2000 65536 65536
13 2000 65536 65536
14 2000 65536 65536
15 2000 65536 65536
16 2000 65536 65536
17 2000 65536 65536
18 2000 65536 65536
19 2000 65536 65536
20 2400 65536 65536
21 2400 65536 65536
22 2400 65536 65536
23 2400 65536 65536
24 2400 65536 65536
25 2400 65536 65536
26 2400 65536 65536
27 2400 65536 65536
28 2400 65536 65536
29 2400 65536 65536