贴个Python代码,这个题疑似Python过不了
查看原帖
贴个Python代码,这个题疑似Python过不了
1077867
SwordRain楼主2024/3/25 17:17
import sys
input = lambda: sys.stdin.readline().strip()
def find(x, s):
    if x != s[x]:
        s[x] = find(s[x], s)
    return s[x]
def merge(x, y, s):
    x = find(x, s)
    y = find(y, s)
    s[x] = y
def kruskal(edges, n, s, total):
    ans = 0
    i = 1
    j = 0
    while j < len(edges) and i != n:
        start, end, weight = edges[j]
        if find(start, s) != find(end, s):
            merge(start, end, s)
            ans += weight
            i += 1
        j += 1
    print(total - ans)
def main():
    while True:
        n, m = map(int, input().split())
        if n == m == 0:
            sys.exit()
        edges = []
        total = 0
        for _ in range(m):
            edges.append(list(map(int, input().split())))
            total += edges[_][2]
        kruskal(sorted(edges, key=lambda a: a[2]), n, [i for i in range(n)], total)
main()
2024/3/25 17:17
加载中...