1584. 連接所有點的最小費用

前置題目：P3366 最小生成樹

思路

題目要找到連接所有點的最小費用。
任意兩點都要滿足「有且僅有」一條簡單路徑。
更精確來說，每個點之間都要有辦法抵達任意其他點，而路徑不一定要一步到位。
而最小生成樹就滿足這個條件，只要對模板稍做修改，就滿足條件了。

程式碼

1. 最小生成樹 Kruskal

struct Edge {
    int u, v, w;
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator<(const Edge& other) const {
        return this->w < other.w;
    }
};
class Solution {
private:
    static const int MX = 1001;
    int parent[MX];
    int setSize[MX];
    void build(int n) {
        iota(parent, parent + n, 0);
        fill(setSize, setSize + n, 1);
    }
    int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    bool isSameSet(int u, int v) {
        return find(u) == find(v);
    }
    void unite(int x, int y) {
        parent[find(x)] = parent[find(y)];
    }
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        build(n);
        vector<Edge> edges;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                int dist = abs(points[i][0] - points[j][0]) + 
                           abs(points[i][1] - points[j][1]);
                edges.push_back(Edge(i, j, dist));
            }
        }
        sort(edges.begin(), edges.end());
        int edgeCnt = 0;
        int cost = 0;
        for(auto& edge : edges) {
            if(!isSameSet(edge.u, edge.v)) {
                unite(edge.u, edge.v);
                cost += edge.w;
                if(++edgeCnt == n - 1) {
                    break;
                }
            }
        }
        return cost;
    }
};

2. 最小生成樹 Prim

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        using pii = pair<int,int>;
        int n = points.size();
        vector<vector<pii>> graph(n);
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                // i -> j, 花費曼哈頓距離   
                int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                graph[i].push_back({dist, j});
                graph[j].push_back({dist, i});
            }
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq; // 記錄權重，鄰居
        vector<bool> used(n, false);
        used[0] = true;
        int nodeCnt = 1;
        int res = 0;
        for(pii neighbor : graph[0]) {
            pq.push(neighbor);
        }
        while(!pq.empty()) {
            auto [dist, v] = pq.top(); pq.pop();
            if(!used[v]) {
                used[v] = true;
                res += dist;
                if(++nodeCnt == n) {
                    break;
                }
                for(pii neighbor : graph[v]) {
                    pq.push(neighbor); 
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(m\log{m})$
• 空間複雜度：$O(n+m)$