苏世机试小课堂，考研机试不再慌！

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

对每个测试用例，在1行里输出最小的公路总长度。

给出村庄之间的距离，选出最短的距离组合可以连通所有村庄。

最小生成树题目，把所有边存下来，按长度进行排序，记录每个节点的父节点，每次找剩余长度最小的边，并查找边两个端点是不是在同一个集合中，不在的话就加入生成树，在的话就跳过，最后加入n-1条边就可以了。

进入下面的链接提交代码（或点击阅读原文）

至此，这道题我们就已经完成了。

本题是kruskal算法模板题，主要是学习这种思路，学习如何写Find()，unite()，kruskal()函数，代码中的细节也需要自己一点点动手去尝试才能深刻理解。

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导

[版权声明] 本站所有资料由用户提供并上传，若内容存在侵权，请联系邮箱。资料中的图片、字体、音乐等需版权方额外授权，请谨慎使用。网站中党政主题相关内容(国旗、国徽、党徽)仅限个人学习分享使用，禁止广告使用和商用。