公路村村通python 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N(≤1000)和候选道路数目M

这是一道经典的最小生成树问题，可以使用 Kruskal 或 Prim 算法来解决。以下是 Kruskal 算法的主要思路：

1. 将所有的边按照权值从小到大排序；
2. 依次选择权值最小的边，如果这条边的两个端点不在同一个连通块中，则将它们合并，直到全部的点都在同一个连通块中。

以下是 Python 代码示例：

# 定义边的结构体
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 并查集
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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):
        self.parent[self.find(x)] = self.find(y)

# Kruskal算法
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x.w)
    res = 0
    count = 0
    for e in edges:
        if uf.find(e.u) != uf.find(e.v):
            uf.union(e.u, e.v)
            res += e.w
            count += 1
            if count == n - 1:
                break
    return res

# 主程序
if __name__ == '__main__':
    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        u, v, w = map(int, input().split())
        edges.append(Edge(u - 1, v - 1, w))
    print(kruskal(n, edges))

其中，输入格式为第一行两个正整数 N 和 M，表示城镇数目和候选道路数目；接下来 M 行每行三个正整数 u、v、w，表示 u 和 v 之间的道路建设成本为 w。输出最小的建设成本即可。