b483.
史蒂芙的觀察日記
內容
背景
史蒂芙在學院讀書時，教授曾經教過最小生成樹 (Minimum Spanning Tree，簡稱 MST)，MST 最常見到的兩個算法 Kruskal's Algorithm、Prim's Algorithm，還有其他的算法來得到 MST。
在某一次作業中，史蒂芙被特別指派的某一道題目，題目描述「給定好一棵 MST，接著新增加一條邊，請問新的最小生成樹成本為何。」聰明的史蒂芙想到一個樸素的解法「增加新的一條邊若造成 MST 上存在一個環，只要把環上最權重最大的邊移除，最小生成樹就大功告成。」
萬萬沒想到，正高興地要拿著 $O(V)$ 算法交差時，卻沒想到一連串的詢問，於是史蒂芙被命令回去觀察觀察一番再交出報告。
「看來史蒂芙還是只有被欺負的份呢。」
題目描述
給定 $N$ 個點、$M$ 條雙向邊，依序給定每一條邊，每增加一條邊，輸出當前的最小生成樹成本，若圖不連通，則輸出最小生成森林成本。
輸入說明
有多組測資，每一組測資第一行有兩個整數 $N, M$。
接下來會有 $M$ 行，每一行上會有三個整數 $x, \; y, \; v$，表示依序加入的無向邊，點 $x$ 連接到點 $y$ 成本為 $v$。節點編號為 $1 \cdots N$。
- $2 \le N \le 100000, \; 1 \le M \le 100000$
- $1 \le x, y \le N, \; 1 \le v \le 30000$
輸出說明
對於每一組測資，第一行輸出 `Case #id`，接著輸出 $M$ 行依序加入邊產生出的最小生成樹成本。
範例輸入
#1
3 3 1 2 1 1 3 2 2 3 4 5 7 1 2 9 2 3 8 3 4 7 4 5 6 2 4 5 1 4 4 2 5 3
範例輸出
#1
Case #1 1 3 3 Case #2 9 17 24 30 27 22 19
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <10M
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <10M
提示 ：
標籤:
出處:
[管理者：
morris1028
(碼畜)
]