1211 . 圖論 之 最小生成樹

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

青い猫

User's AC Ratio

90.4% (464/513)

Submission's AC Ratio

32.6% (878/2691)

Tags

TIOJcon 2008-TIOJcon-3rd

Description

給你一個加權的無向圖（weighted undirected graph），請問這個圖的最小生成樹（minimum spanning tree）的權重和為多少？

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數 n,m(1≤n≤10,000,1≤m≤1,000,000)，代表該圖的點數和邊數。
頂點的編號從 1 到 n。
接下來有 m 列，每列用三個整數 i,j,c(1≤i,j≤n,1≤c≤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

Sample Output 1

10
-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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
Submit
Back to Top