最小生成树(模板题)

方法一：普利姆算法（不推荐，然而这道题用的比较舒服）

python版本

#普利姆算法
def prim():
    dis = [float('inf')]*(n+1) #到连接块最短距离
    dis[1] = 0
    res = 0
    for i in range(n):
        lastNode = -1
        for node in range(1,n+1):
            if vis[node] == False and (lastNode == -1 or dis[node] < dis[lastNode]):
                lastNode = node
        vis[lastNode] = True
        res += dis[lastNode]
        for node in range(1,n+1):
            dis[node] = min(dis[node],cost[lastNode][node])

    return res

n = int(input())
cost = [[0]*(n+1)]
vis = [False]*(n+1)
for i in range(1,n+1):
    cost.append([0] + [int(i) for i in input().split()])

print(prim())

方法二：克鲁斯卡尔（本人最爱）

python版本

class UFS():
    def __init__(self,n):
        self.father = {}
        self.size = {}
        for i in range(1,n+1):
            self.father[i] = i
            self.size[i] = 1

    def findRoot(self,node):
        father = self.father[node]
        if father != node:
            father = self.findRoot(father)
        self.father[node] = father
        return father

    def union(self,node_a,node_b):
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)
        if root_a != root_b:
            if self.size[root_a] > self.size[root_b]:
                self.father[root_b] = root_a
                self.size[root_a] += self.size[root_b]
            else:
                self.father[root_a] = root_b
                self.size[root_b] += self.size[root_a]
            return True
        else:
            return False


n = int(input())
ufs = UFS(n)
total = 0
links = []
for i in range(1,n+1):
    temp = [0] + [int(i) for i in input().split()]
    for j in range(i + 1,n+1):
        links.append((i,j,temp[j]))

links = sorted(links,key = lambda x : x[2])
for i in range(len(links)):
    if ufs.union(links[i][0],links[i][1]):
        total += links[i][2]

print(total)