b007:
最小生成樹邊權之和
Content
克魯斯克爾演算法 (Kruskal) 演算法是一種用來尋找最小生成樹的演算法，由 Joseph Kruskal 在1956年發表。
步驟：
- 新建圖G，G中擁有原圖中相同的節點，但沒有邊
- 將原圖中所有的邊按權值從小到大排序
- 從權值最小的邊開始，如果這條邊連接的兩個節點於圖G中不在同一個連通分量中，則添加這條邊到圖G中
- 重複3，直至圖G中所有的節點都在同一個連通分量中
例題參考：克魯斯克爾演算法
Input
第一行 2個整數，分別是 點數 N 和 邊數 M
接下來有 M行，每一行上會有三個整數 u, v, w，依序加入點 u 連接到 點 v, 無向邊權重 w。節點編號為 0 ... N-1。
Output
輸出最小生成樹各邊(u, v, w) 及 權重之和
Sample Input
#1
7 11 0 1 7 0 3 5 1 2 8 1 3 9 1 4 7 2 4 5 3 4 15 3 5 6 4 5 8 4 6 9 5 6 11
Sample Output
#1
(2, 4, 5) (0, 3, 5) (3, 5, 6) (1, 4, 7) (0, 1, 7) (4, 6, 9) 39
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (33%): 1.0s , <1K
不公開 測資點#1 (33%): 1.0s , <1K
不公開 測資點#2 (34%): 1.0s , <1K
不公開 測資點#0 (33%): 1.0s , <1K
不公開 測資點#1 (33%): 1.0s , <1K
不公開 測資點#2 (34%): 1.0s , <1K
Hint ：
Tags:
出處:
[管理者：
admin
(Judge)
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||