蘇世機試小課堂，考研機試不再慌！

繼續(xù)暢通工程

題目描述

某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。請計算最小的公路總長度。

輸入描述

測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數(shù)目N ( < 100 )；隨后的N(N-1)/2行對應村莊間的距離，每行給出一對正整數(shù)，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。

當N為0時，輸入結(jié)束，該用例不被處理。

輸出描述

對每個測試用例，在1行里輸出最小的公路總長度。

輸入

3

1 2 1

1 3 2

2 3 4

4

1 2 1

1 3 4

1 4 1

2 3 3

2 4 2

3 4 5

0

輸出

3

5

答案

①讀題:

給出村莊之間的距離，選出最短的距離組合可以連通所有村莊。

②想出思路：

最小生成樹題目，把所有邊存下來，按長度進行排序，記錄每個節(jié)點的父節(jié)點，每次找剩余長度最小的邊，并查找邊兩個端點是不是在同一個集合中，不在的話就加入生成樹，在的話就跳過，最后加入n-1條邊就可以了。

③動手編程：

④測試樣例：

⑤提交代碼：

進入下面的鏈接提交代碼（或點擊閱讀原文）

https://www.nowcoder.com/practice/d6bd75dbb36e410995f8673a6a2e2229?tpId=40&&tqId=21479&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回評測結(jié)果：

至此，這道題我們就已經(jīng)完成了。

本題總結(jié)

本題是kruskal算法模板題，主要是學習這種思路，學習如何寫Find()，unite()，kruskal()函數(shù)，代碼中的細節(jié)也需要自己一點點動手去嘗試才能深刻理解。

蘇世學社旗下品牌，專注于計算機考研

計算機考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學習分享丨咨詢前輩丨個性化指導