瑞米是隻聰明的老鼠,他知道餐廳裡有哪些地方有捕鼠器
餐廳裡共有 $N$ 個地點是必須常去的地方,他想製作一張地圖給他的家人
$N$ 個地點中任意兩個地點都有路可走,但是其中有 $m$ 條路有捕鼠器
他想盡可能的避開這些有捕鼠器的路,好規劃一個較安全的地圖
小林想要協助他製作地圖,正好他過去曾有寫程式的經歷(?)
地圖兩兩地點間至少要有一條路徑,該地圖最少可以容許幾個有捕鼠器的路?
(這裡路徑表示地點序列,使得一個地點與下個地點之間有路)
第一列有兩個數 $N, m$ 分別為地點數以及有幾條捕鼠器的路 $(1 \le N \le 5\cdot 10^5, 0 \le m \le \min(5\cdot 10^5, \frac{N(N-1)}{2}))$
接著有 $m$ 列 $a_i, b_i$,表示地點 $a_i$ 與 $b_i$ 間的路中有捕鼠器 $(1 \le a_i, b_i \le N, a_i \not= b_i)$
任兩地點間要有一條路徑的地圖最少能有幾個有捕鼠器的路
第一筆範測可由下圖表示:
其中一種最少捕鼠器路的地圖可用 $3$ 條路: $\{1, 2\}, \{4, 2\}, \{3, 2\}$ 所構成,且任意兩點存在一條路徑
CODEFORCES 1243D 0-1 MST
No. | Testdata Range | Score |
---|---|---|
1 | 0~45 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 2000 | 524288 | 65536 | |
1 | 2000 | 524288 | 65536 | |
2 | 2000 | 524288 | 65536 | |
3 | 2000 | 524288 | 65536 | |
4 | 2000 | 524288 | 65536 | |
5 | 2000 | 524288 | 65536 | |
6 | 2000 | 524288 | 65536 | |
7 | 2000 | 524288 | 65536 | |
8 | 2000 | 524288 | 65536 | |
9 | 2000 | 524288 | 65536 | |
10 | 2000 | 524288 | 65536 | |
11 | 2000 | 524288 | 65536 | |
12 | 2000 | 524288 | 65536 | |
13 | 2000 | 524288 | 65536 | |
14 | 2000 | 524288 | 65536 | |
15 | 2000 | 524288 | 65536 | |
16 | 2000 | 524288 | 65536 | |
17 | 2000 | 524288 | 65536 | |
18 | 2000 | 524288 | 65536 | |
19 | 2000 | 524288 | 65536 | |
20 | 2000 | 524288 | 65536 | |
21 | 2000 | 524288 | 65536 | |
22 | 2000 | 524288 | 65536 | |
23 | 2000 | 524288 | 65536 | |
24 | 2000 | 524288 | 65536 | |
25 | 2000 | 524288 | 65536 | |
26 | 2000 | 524288 | 65536 | |
27 | 2000 | 524288 | 65536 | |
28 | 2000 | 524288 | 65536 | |
29 | 2000 | 524288 | 65536 | |
30 | 2000 | 524288 | 65536 | |
31 | 2000 | 524288 | 65536 | |
32 | 2000 | 524288 | 65536 | |
33 | 2000 | 524288 | 65536 | |
34 | 2000 | 524288 | 65536 | |
35 | 2000 | 524288 | 65536 | |
36 | 2000 | 524288 | 65536 | |
37 | 2000 | 524288 | 65536 | |
38 | 2000 | 524288 | 65536 | |
39 | 2000 | 524288 | 65536 | |
40 | 2000 | 524288 | 65536 | |
41 | 2000 | 524288 | 65536 | |
42 | 2000 | 524288 | 65536 | |
43 | 2000 | 524288 | 65536 | |
44 | 2000 | 524288 | 65536 | |
45 | 2000 | 524288 | 65536 |