1168. Optimize Water Distribution in a Village

MST O((V+E)log(V+E)) time O(V) space
这道题首先应该想到是求MST，然后思考如何抽象每个点来构造MST，观察到pipes里每个点都是1-indexed，说明应该有一个点0，解法就是加一个virtual node 0，把每个点自己的weight放到和0连起来的边上，就构成了一棵完整的0-indexed的图，求这个图的MST即可

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        vector<tuple<int, int, int>> edges;
        for (int i = 0; i < n; ++i) {
            edges.emplace_back(wells[i], 0, i + 1);
        }
        for (const auto &p : pipes) {
            edges.emplace_back(p[2], p[0], p[1]);
        }
        sort(begin(edges), end(edges));
        parent.resize(n + 1);
        iota(begin(parent), end(parent), 0);
        int res = 0;
        for (const auto &[w, u, v] : edges) {
            if (merge(u, v)) {
                res += w;
            }
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }

    vector<int> parent;
};