LeetCode每日一题：连接所有点的最小费用

传送门

思路

题意挺简单的，就是在一个直角坐标系内给出若干点，求一个最小生成树，可以用prim直接写，也可以建图用 并查集维护边集再Kruskal。二者的介绍详见博客：最小生成树–Prim算法&Kruskal算法。

代码

prim

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        const int n = points.size();
        int ans = 0, mp[1005][1005], dis[1005];
        bool flag[1005]={0};
        memset(dis, 0x3f, sizeof(dis));
        
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) {
                mp[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            }
        }

        for (int i = 0; i < n; i++) {
            int tmp = -1;
            for (int j = 0; j < n; j++) {
                if (!flag[j] && (tmp == -1 || dis[tmp] > dis[j])) {
                    tmp = j;
                }
            }

            if(i) {
                ans += dis[tmp];
            }
            flag[tmp] = true;
            for(int j = 0; j < n; j++) {
                if(!flag[j]) {
                    dis[j] = min(dis[j], mp[tmp][j]);
                }
            }
        }

        return ans;
    }
};

Kruskal

struct Edge {
    int len, x, y;
    Edge(int len, int x, int y) : len(len), x(x), y(y) {}
};

class Solution {
private:
    unordered_map<int, int> father;
    unordered_map<int, int> rank;
    vector<Edge> edges;
public:
    void init(int n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    bool merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);

        if (fx == fy) {
            return false;
        }

        if(rank[fx] < rank[fy]) {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        father[fy] = fx;
        return true;
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        auto dis = [&](int x, int y) -> int {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        const int n = points.size();
        int cnt = 1, ans = 0;
        init(n);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.emplace_back(dis(i, j), i, j);
            }
        }
        sort(edges.begin(), edges.end(), [](Edge a, Edge b) -> bool {
            return a.len < b.len;
        });

        for (auto& [len, x, y] : edges) {
            if(merge(x, y)) {
                ans += len;
                cnt++;
                if(cnt == n) {
                    break;
                }
            }
        }

        return ans;
    }
};