d106:
P_7_12 最小生成樹 (*)
Content
樹是沒有環路的連通圖，對於一個圖 G，它的一個生成樹(spanning tree)是指挑選 G 的一些邊，將所有點連成一個連通區塊，而挑選的邊形成的是一個樹。因為 n 個點至少要 (n-1) 個邊才能形成一個連通區塊，而超過 (n-1) 個邊必然會造成有環路，所以一定恰好是 (n-1) 個邊。G 的最小生成樹(minimum spanning tree)是指邊的權重總和最小的生成樹。
假設我們有 n 個城市，要建設一個交通網路將 n 個城市連起來，如果圖 G 的每一個邊代表一條可以建設的道路，而邊上有一個非負的權重代表該道路的建設成本，那麼最小生成樹就是最低的建設總成本。
下圖是一個例子，其中實線代表最小生成樹的邊，虛線代表沒有挑選的邊，圖中有 8 個點，一定剛好有 7 個邊。
輸入一個無向圖 G=(V, E, w)，其中點以 0 ~ (n-1)編號，而邊的權重是非負整數。
計算G的最小生成樹的成本。兩點之間可能有多個邊。
Input
第一行是兩個正整數 n 與 m ，代表點數與邊數，接下來有 m 行，每行三個整數 u, v, w 代表一條無向邊 (u,v) 的長度是 w。
n 不超過 104，m 不超過 105, w 是不超過 104 的非負整數。
Output
輸出最小生成樹的成本，如果不存在則輸出 -1。
Sample Input
#1
8 10 0 1 6 0 2 4 1 2 5 2 3 9 1 4 1 1 5 1 2 6 2 4 5 3 5 6 8 7 6 1
Sample Output
#1
23
Sample Input
#2
4 3 2 1 5 1 0 0 0 2 1
Sample Output
#2
-1
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint ：
範例一是本小節說明所用的例子。
測資中前兩筆的 n 不超過 500。
計算最小生成樹有多個演算法，目前比較常用的有兩個：Prim 演算法與 Kruskal 演算法。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||