HDU 6187 Destroy Walls(并查集)

题意: 给定n个点,m条边,实现将全部点连通(最小生成树),即去掉回路(环),所需的最少费用。 思路: n太大,prim算法会超时。 使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大的权值用来合并,剩下的小权值的边便能使得拆除时所用的费用尽量小。 #include #include #include #include #include #include #include #include #include #define inf 0x7