Kruskal 板子题

解题思路:

注意事项:

参考代码:

n=int(input())

edge=[]

st=[False]*(n+1)

a=[]

p=[0]*(n+1)

for _ in range(n):

    w=a.append(list(map(int,input().split())))

for i in range(1,n+1):

    for j in range(1,n+1):

        edge.append((i,j,a[i-1][j-1]))

def find(x):

    if p[x]!=x:

        p[x]=find(p[x])

    return p[x]

def Kruskal():

    res=0

    cnt=0

    for i in range(1,n+1):

        p[i]=i

    edge.sort(key=lambda x:x[2])

    for x in edge:

        u,v,w=x[0],x[1],x[2]

        if find(u)!=find(v):

            res+=w

            p[find(u)]=find(v)

            cnt+=1

    if cnt==n:return float('inf')

    return res

print(Kruskal())