请编写c++语言程序完成下列问题：题目描述某省调查乡村交通状况得到的统计表中列出了任意两村庄间的距离。省政府畅通工程的目标是使全省任何两个村庄间都可以实现公路交通但不一定有直接的公路相连只要能间接通过公路可达即可并要求铺设的公路总长度为最小。请计算最小的公路总长度。输入测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N 100 ；随后的NN-12行对应村庄间的距离每行给出一对正整数分

算法1

(Prim算法)

Prim算法使用堆优化和邻接表的方法，可以在O(nlogn)的时间内解决最小生成树问题。

时间复杂度

O(nlogn)

参考文献

大话数据结构

C++ 代码

算法2

(Kruskal算法)

Kruskal算法是一种贪心算法，用来生成最小生成树。Kruskal算法的基本思想是从小到大加入边，直到构建出来的边形成一个树为止。如果加入的边形成了环，那么就不加入这条边。

时间复杂度

O(nlogn)

参考文献

大话数据结构

C++ 代码