#P350. 最小生成樹
-
ID: 350
Type: Default
3000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> 最小生成樹
題目描述
給你一個加權的無向圖(weighted undirected graph)，請問這個圖的最小生成樹(minimum spanning tree)的權重和為多少？
學習參考：
輸入格式
輸入可能包含多筆測試資料，以EOF作為結束。
每筆測試資料的第一列有兩個整數n,m(1<=n<=100；0<=m<=200)，代表該圖的點數和邊數。
頂點的編號從0到n-1。
接下來有m列，每列用三個整數i,j,c(0<=i,j<n；c為int可儲存的非負整數)描述一條邊，i,j為兩個端點的編號，c為其權重。
輸出格式
對於每筆測試資料，請輸出最小生成樹的權重和。如果圖不連通，請輸出 -1。
Samples
3 3
0 1 5
1 2 5
2 0 10
4 2
1 2 5
2 3 5
10
-1
提示
最小生成樹, minimum spanning tree
原始資料
- Zero1 題號：
a350 - Hydro 題號：
Z0350 - Locale：
zh_TW - Display：
open