分步的最小生成树

主要先把必选的边连进去，再把其他边按最小生成树接上

1. 输入时把必选边和其他边分开

2. 先用克鲁斯卡尔连必选边

3. 其他边按照最小生成树做法完成连接

python版本

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

    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

        return False



n,m = map(int,input().split())
bi = []
other = []
for i in range(m):
    a,b,c,d = map(int,input().split())
    if a == 1:
        bi.append((b,c,d))
    else:
        other.append((b,c,d))


other = sorted(other,key = lambda x : x[2] )



ufs  = UFS(n)

res = 0
for var in bi:
    ufs.union(var[0],var[1])
    res += var[2]

for var in other:
    if ufs.union(var[0],var[1]):
        res += var[2]

print(res)