昨天我們看了kruskal演算法，今天我們換種演算法來求。仍然是洛谷上的題目。
14856: 線路規劃
時間限制: 1 Sec 內存限制: 128 MB
題目描述
有n 個村莊之間需要架設通信線路，使得任意兩個村莊之間均可通信。兩個村莊a， b 間可通信，當且僅當它們之間存在一條通信線路或者存在村莊c 使得a，c 和b，c 間均可通信。給出村莊之間架設通信線路的代價，求出最小的總代價。
輸入
第一行包含兩個整數n，m，分別表示村莊數量和可以架設通信線路的村莊對數。以下m 行，每行三個整數a，b，c，表示村莊a，b之間架設線路的代價為c（村莊從0 開始編號）。
輸出
一個整數，最小總代價。
樣例輸入
3 30 1 11 2 12 0 3
樣例輸出
2
提示
對於50% 的數據，n<=100，m <=n^2
對於全部數據，1<=n<=10^5; n-1<=m<=10^5，所有代價均在[0， 10^6] 範圍內，保證問題有解。
題目大意就是給n個點，m對長度，求一個最小生成樹。
這個過程和Dijstra非常類似，也可以用堆優化。大家現在自己獨立思考一下。這個演算法和Dijstra有什麼相同點？還有什麼不同點？可以把你的答案放到評論區內！！
Prim堆優化的演算法複雜度為O(E+VlgV)
我們再綜合看一下Prim和Kruscal兩個演算法。其實兩種演算法的複雜度級別是差不多的。Kruscal需要並查集知識的前置，但Prim不需要。兩者的核心思想其實都是貪心，只不過貪心所用的策略和方式不同。很難說孰優孰劣，所以大家針對不同的題型或者針對自己的個人喜好自行選用就行。舉報
原創文章，作者：投稿專員，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/226768.html
微信掃一掃 
支付寶掃一掃 