a129: 最小生成樹
Tags :
Accepted rate : 541人/607人 ( 89% ) [非即時]
評分方式:
Strictly

最近更新 : 2011-05-15 13:38

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 , <50M
Hint :

overflow..?

//范例测资已更正。——liouzhou_101

 //thanks =P, shik 

Tags:
出處:


ID User Problem Subject Hit Post Date
25690 luray0601@gm...(QWERTYPIG) a129
c++
597 2021-06-13 12:40