昨日大家看过kruskal优化算法，今日大家换个优化算法去求。依然是洛谷上的题型。
14856: 路线整体规划
时间限制: 1 Sec 运行内存限定: 128 MB
题型叙述
有n 个村庄中间必须架设通信线路，促使随意2个村庄中间均可通讯。2个村庄a， b 间可通讯，当且仅当他们相互之间存有一条通信线路或是存有村庄c 促使a，c 和b，c 间均可通讯。得出村庄中间架设通信线路的代价，求出最少的总代价。
键入
第一行包括2个整数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和Kruscal2个优化算法。实际上二种优化算法的复杂性等级是类似的。Kruscal必须并查集专业知识的外置，但Prim不用。二者的核心内容实际上全是贪婪，只不过是贪婪常用的对策和方法不一样。不好说孰优孰劣，因此大伙儿对于不一样的题目或是对于自身的个人爱好自主采用就可以了。检举
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
