a350: 最小生成樹
Tags : minimum spanning tree 最小生成樹
Accepted rate : 22人/27人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-10-24 15:12

Content

給你一個加權的無向圖(weighted undirected graph),請問這個圖的最小生成樹(minimum spanning tree)的權重和為多少?

 

學習參考:

圖形演算法-最小生成樹

 

Input

輸入可能包含多筆測試資料,以EOF作為結束。 

每筆測試資料的第一列有兩個整數n,m(1<=n<=100,000;0<=m<=200,000),代表該圖的點數和邊數。 

頂點的編號從0到n-1。 

接下來有m列,每列用三個整數i,j,c(0<=i,j<n;c為int可儲存的非負整數)描述一條邊,i,j為兩個端點的編號,c為其權重。 

Output

對於每筆測試資料,請輸出最小生成樹的權重和。如果圖不連通,請輸出 -1。

Sample Input #1
3 3
0 1 5
1 2 5
2 0 10
4 2
1 2 5
2 3 5
Sample Output #1
10
-1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1K
Hint :

最小生成樹, minimum spanning tree

Tags:
minimum spanning tree 最小生成樹
出處:
[管理者:
admin (Judge)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」