pat7-107-10 公路村村通

这道题是一道最小生成树的经典问题。题目描述为：有n个村庄需要修路相连，给出每个村庄之间修路的代价，求使得所有村庄都联通的最小代价。

解决这个问题的算法有很多，其中一个经典的算法是Kruskal算法。这个算法的基本思想是先将所有的边按照代价从小到大排序，然后依次加入到最小生成树的集合中，如果加入这条边不会形成环路，就将这条边加入最小生成树集合中。

具体实现时，可以使用并查集来检查是否形成环路。

代码实现可以参考下面这段Python代码：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        self.parent[self.find(i)] = self.find(j)

def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    res = 0
    for i, j, w in edges:
        if uf.find(i) == uf.find(j):
            continue
        uf.union(i, j)
        res += w
    return res

其中n表示村庄的数量，edges表示每个村庄之间修路的代价，是一个三元组(i,j,w)，表示村庄i和村庄j之间修路的代价为w。

使用这个算法可以解决这道题目，时间复杂度为O(mlogm)，其中m表示边的数量。