请问这道题python为什么有三个TLE呢 kruskal算法
查看原帖
请问这道题python为什么有三个TLE呢 kruskal算法
497577
zzuBobby楼主2021/4/10 15:59
import operator


class Edge:
    def _init_(self, u, v, w):
        self.U = u
        self.V = v
        self.W = w


def find(u):
    if S[u] == u:
        return u
    else:
        return find(S[u])


def kruskal():
    ans = 0
    bound = 0
    # 并查集初始化
    for i in range(1, n+1):
        S[i] = i

    # 每次寻找最短且无环边
    s_edge = sorted(edge, key=operator.attrgetter('W'))
    for i in range(1, m+1):
        b = find(s_edge[i].U)
        c = find(s_edge[i].V)
        if b == c:
            continue
        else:
            S[c] = b
            ans += s_edge[i].W
            bound += 1
            if bound == (n - 1):
                break
    return ans


n, m = map(int, input().split())  # 点数 边数
un = Edge()
un.U, un.V, un.W = 0, 0, 0

if m >= (n - 1):  # 连通

    # 并查集定义
    S = [0 for i in range(n+1)]

    # 边集的定义
    edge = [un]
    for i in range(1, m+1):
        t = Edge()
        t.U, t.V, t.W = map(int, input().split())
        edge.append(t)

    # 调用算法
    res = kruskal()
    print(res)

else:
    print('orz')
2021/4/10 15:59
加载中...