这五个点连起来最少要多少

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

主连通块有五个点、五条边: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)))
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论