正在展开冲刺页面
正在展开冲刺页面
按边权排序并用并查集避免成圈。
带权无向边。
总造价。
管网、线路铺设。
完整可运行代码
edges = [(1, 0, 1), (2, 0, 2), (2, 1, 2), (3, 1, 3), (4, 2, 3)]
parent = [0, 1, 2, 3]
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0
for w, u, v in sorted(edges):
a, b = find(u), find(v)
if a != b:
parent[a] = b
total += w
print(total)