这五个点连起来最少要多少
主连通块有五个点、五条边:0-1:2 0-2:1 1-3:3 2-4:9 3-4:1。运行下面这段程序,看最小总长和用了几条边:
def make(verts):
return {u: u for u in verts}
def find(p, x):
while p[x] != x:
p[x] = p[p[x]]
x = p[x]
return x
def union(p, a, b):
ra, rb = find(p, a), find(p, b)
if ra == rb:
return False
p[ra] = rb
return True
def kruskal(edges, verts):
p = make(verts)
total = 0
picked = []
for a, b, w in sorted(edges, key=lambda e: (e[2], e[0], e[1])):
if union(p, a, b):
total += w
picked.append((a, b))
return total, picked
t, p = kruskal([(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)], [0, 1, 2, 3, 4])
print(str(t) + "/" + str(len(p)))
全部评论