?

HDU 4081 Qin Shi Huang's National Road System（次小生成樹-Kruskal）

博主的方法很好，但是有疑問，為什么不能將最多人口的兩城市的距離設置為0，在進行Prim操作，求B呢？這個將在后續的刷題中體現。

POJ 2377 Bad Cowtractors（最大生成樹-Kruskal）

裸題，可以用來熟悉算法。

HDU 6141 I am your Father!（最小樹形圖）

朱劉算法，這個還不會，稍后來填坑。

CodeForces 609 E.Minimum spanning tree for each edge（最小生成樹-Kruskal+在線倍增LCA）

在線倍增LCA，等等再回來填坑

HDU 2121 Ice_cream’s world II（最小樹形圖）

朱劉算法

HDU 4009 Transfer water（最小樹形圖）

朱劉算法

POJ 1258 Agri-Net（最小生成樹-Prim）

最小生成樹裸題！

POJ 3723 Conscription（最小生成樹-Kruskal）

這個題是說招募兵，然后親密關系會減少招募的花費，這個題一開始的思路是并查集，但是后來想，對于因為親密關系程度不一樣，所以還是得用最小生成樹，考慮過是不是要枚舉節點，后來明白了，不需要根節點，最小生成樹生成后根節點也就確定了，所以就沒必要了，直接親密程度設成負值，一遍最小生成樹。

POJ 3026 Borg Maze（bfs+最小生成樹-Prim）

這個題，是說有一個像史萊姆一樣的的怪物，會向四個方向分裂，求分裂的最小次數，也就是說重復的路只算一次，那么我一開始想到的最短路就不對了，因為重復的路徑不算，那么也就是說是找的一顆最小生成樹，那么需要找到任意兩點的距離，但是我看他們只用了一遍BFS，然后搜了搜題解，發現自己看錯了，確實是N2遍。

POJ 1789 Truck History（最小生成樹-Prim）???????

最小生成樹變形，每個字符串不一樣的字符數是距離，然后求最小生成樹，字符串判等，暴利即可。

POJ 2485 Highways（最小生成樹-Prim）

一遍最小生成樹，然后標記最大邊輸出即可。

?

?

?

總結

以上是生活随笔為你收集整理的2019.9.18最小生成树知识点总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。