最小生成树

模板题

被去除网线长度最大即剩下的联通区域最小，即求一颗最小生成树

结果为所有边的长度去掉最小生成树的所有边长

这里我用的克鲁斯卡尔，写着顺手，速度还快

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,m = map(int,input().split())
ufs = UFS(n)
data = []
total = 0
for i in range(m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))
    total += c
data = sorted(data,key = lambda x : x[2])

res = 0
for i in range(m):
    if ufs.union(data[i][0],data[i][1]):
        res += data[i][2]

print(total - res)