公路村村通python

公路村村通问题是一道经典的最小生成树问题，可以使用Kruskal算法或Prim算法来解决。是Kruskal算法的Python实现示例：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

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

其中，UnionFind类定义了并查集数据结构，用于判断两个节点是否在同一连通块中；kruskal函数实现了Kruskal算法，用于求解最小生成树的权值和。输入参数n表示图中节点的数量，edges是一个列表，每个元素表示一条边，包括起点、终点和权值。输出结果为最小生成树的权值和。

具体使用时，可以按照题目要求先读入数据，然后调用kruskal函数求解最小生成树的权值和。