1211 . 圖論 之 最小生成樹
TopCoder
Tags
Description
給你一個加權的無向圖（weighted undirected graph），請問這個圖的最小生成樹（minimum spanning tree）的權重和為多少？
Input Format
輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數 $n,m (1 \le n \le 10,000, 1 \le m \le 1,000,000)$，代表該圖的點數和邊數。
頂點的編號從 $1$ 到 $n$。
接下來有 $m$ 列，每列用三個整數 $i,j,c (1 \le i,j \le n, 1 \le c \le 1,000)$ 描述一條邊，$i, j$ 為兩個端點的編號，$c$ 為其權重。
當 $n=m=0$ 時代表輸入結束。
Output Format
對於每筆測試資料，請輸出最小生成樹的權重和。如果圖不連通，請輸出 $-1$。
Sample Input 1
3 3
1 2 5
2 3 5
3 1 10
4 2
1 2 5
2 3 5
0 0
1 2 5
2 3 5
3 1 10
4 2
1 2 5
2 3 5
0 0
Sample Output 1
10
-1
-1
Hints
Problem Source
原 TIOJ1211 / TIOJ 2008 例行賽 03 (prob C)。經典問題練習。Problem Setter：Tmt。
2024/03/17 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |