前往
大廳
主題

ZeroJudge - f678: FJCU_109_Winter_Day3_Lab2 最小生成樹練習 解題心得

Not In My Back Yard | 2021-03-07 00:00:06 | 巴幣 0 | 人氣 262

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M (範圍未知,經測不超過 100),代表有一個圖,其有 N 個節點(編號為 0 ~ n - 1)以及 M 條邊。接著 M 列輸入,每列給定三整數 u 、 v 、 w(0 ≦ u 、 v < N),代表節點 u 與節點 v 有一條權重為 w 之邊。

求這個圖的最小生成樹(Minimum Spanning Tree)上的邊權重之總和。



範例輸入:
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


範例輸出:
39


解題思維:
最小生成樹之作法參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作