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

继续畅通工程

题目描述

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

输入描述

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

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

输出描述

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

输入

3

1 2 1

1 3 2

2 3 4

4

1 2 1

1 3 4

1 4 1

2 3 3

2 4 2

3 4 5

0

输出

3

5

答案

①读题:

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

②想出思路：

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

③动手编程：

④测试样例：

⑤提交代码：

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

https://www.nowcoder.com/practice/d6bd75dbb36e410995f8673a6a2e2229?tpId=40&&tqId=21479&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回评测结果：

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

本题总结

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

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

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

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