創作內容

0 GP

ZeroJudge - d909: 公路局長好煩惱!? 解題心得

作者:Not In My Back Yard│2019-04-20 23:07:16│贊助:0│人氣:18
題目連結:


題目大意:
給定兩正整數 N 、 M (N ≦ 10, 000 , M ≦ N × (N - 1) ÷ 2),代表有 N 個城鎮(城鎮編號由 0 ~ N - 1),而現在有 M 條可興建的路。

接著的 M 列輸入,每列給定三正整數 A 、 B 、 C ,代表城鎮 A 跟城鎮 B 之間可以建一條路,成本為 C 。

求把所有城鎮連起來所需的最小成本為何?



範例輸入:
5 10
0 2 20
2 4 31
4 1 38
1 3 23
3 0 6
0 4 22
3 2 8
1 2 4
3 4 1
1 0 8


範例輸出:
19


解題思維:
本題即是最小生成樹,作法參見以前的文章

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4365917
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|並查集(Disjoint Set)|圖論

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

asd22552158悠閒的巴友
小說還是沒有更新看更多我要大聲說19小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】