用Python写一个程序并有输出结果利用并查集的思想求解最小生成树的问题。输入格式: n, e :n端点数量、m边的数量 n1,n2,e1:1端点1,n2端点2 e1边的权值 这样的信息有e行 输出格式: n1 n2 e1 生成树中的边的信息生成树的权值之和即最小成本。
时间: 2024-02-11 20:04:52 浏览: 13
这个问题的解法和上一个问题是一样的,只是输入格式略有不同。下面是根据你提供的输入格式编写的程序:
```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 = sorted(edges, key=lambda x: x[2])
mst = []
cost = 0
for e in edges:
if uf.union(e[0], e[1]):
mst.append(e)
cost += e[2]
return mst, cost
if __name__ == '__main__':
n, m = map(int, input().split())
edges = []
for i in range(m):
u, v, w = map(int, input().split())
edges.append((u - 1, v - 1, w))
mst, cost = kruskal(n, edges)
for e in mst:
print(e[0] + 1, e[1] + 1, e[2])
print(cost)
```
这个程序的思路和上一个程序相同,只是在读入输入时需要分别读入起点、终点和边权,然后将起点和终点都减去1,以便于在程序中使用0-based索引。在输出时,我们也将起点和终点都加上1,以便于和输入格式相符。
希望这个程序能够帮助你解决问题,如果你还有其他问题,欢迎提问。