1584.连接所有点的最小费用

付费题

一、最小生成树

#并查集实现略
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        graph = []	# 无向图（i，j，w），ij为结点，w为权值
        n = len(points)
        # 遍历每两个点的组合，构造边集
        for i in range(n):
            xi, yi = points[i][0], points[i][1]
            for j in range(i):
                xj, yj = points[j][0], points[j][1]
                w = abs(xi-xj) + abs(yi-yj)	#曼哈顿距离
                graph.append((i, j, w))
        graph.sort(key = lambda x : x[2])	#按权值排序
        uf = UnionFind(n)
        res = 0
        for i, j, w in graph:
            if not uf.isConnected(i, j):
                uf.union(i, j)
                res += w
        return res if uf.count == 1 else -1