Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1168.html

1168. Optimize Water Distribution in a Village

Level

Hard

Description

There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.

For each house i, we can either build a well inside it directly with cost wells[i], or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes, where each pipes[i] = [house1, house2, cost] represents the cost to connect house1 and house2 together using a pipe. Connections are bidirectional.

Find the minimum total cost to supply water to all houses.

Example 1:

Image text

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]

Output: 3

Explanation:

The image shows the costs of connecting houses using pipes.

The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

Constraints:

  • 1 <= n <= 10000
  • wells.length == n
  • 0 <= wells[i] <= 10^5
  • 1 <= pipes.length <= 10000
  • 1 <= pipes[i][0], pipes[i][1] <= n
  • 0 <= pipes[i][2] <= 10^5
  • pipes[i][0] != pipes[i][1]

Solution

Create a virtual node with number 0, which connects to each of the n nodes with cost wells[i] if the house number is i + 1. Then the problem becomes a minimum spanning tree problem.

Use Kruskal’s algorithm to obtain a minimum spanning tree. First use a new array to store all the edges, including the newly added edges, and sort the edges according to weights in ascending order. Then loop over the edges in sorted order. For each edge, if the two nodes are not in the same component, then connect them and add the cost to the total cost, with the nodes’ components updated. Finally, return the total cost.

  • class Solution {
    private int[] p;

    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        int[][] all = new int[pipes.length + n][3];
        int idx = 0;
        for (int[] pipe : pipes) {
            all[idx++] = pipe;
        }
        for (int j = 0; j < n; ++j) {
            all[idx++] = new int[] {0, j + 1, wells[j]};
        }
        p = new int[n + 1];
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
        }
        Arrays.sort(all, Comparator.comparingInt(a -> a[2]));
        int res = 0;
        for (int[] e : all) {
            if (find(e[0]) == find(e[1])) {
                continue;
            }
            p[find(e[0])] = find(e[1]);
            res += e[2];
            --n;
            if (n == 0) {
                break;
            }
        }
        return res;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

  • // OJ: https://leetcode.com/problems/optimize-water-distribution-in-a-village/
// Time: O(E + (V + E) * log(V + E))
// Space: O(E + V)
class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& W, vector<vector<int>>& P) {
        vector<vector<pair<int, int>>> G(n);
        for (auto &p : P) {
            int u = p[0] - 1, v = p[1] - 1, cost = p[2];
            G[u].emplace_back(v, cost);
            G[v].emplace_back(u, cost);
        }
        unordered_set<int> seen;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // cost, index
        for (int i = 0; i < n; ++i) pq.emplace(W[i], i);
        int ans = 0;
        while (seen.size() < n) {
            auto [cost, u] = pq.top();
            pq.pop();
            if (seen.count(u)) continue;
            seen.insert(u);
            ans += cost;
            for (auto &[v, c] : G[u]) {
                if (seen.count(v)) continue;
                pq.emplace(c, v);
            }
        }
        return ans;
    }
};

  • class Solution:
    def minCostToSupplyWater(
        self, n: int, wells: List[int], pipes: List[List[int]]
    ) -> int:
        for i, w in enumerate(wells):
            pipes.append([0, i + 1, w])
        pipes.sort(key=lambda x: x[2])

        p = list(range(n + 1))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        res = 0
        for u, v, w in pipes:
            if find(u) == find(v):
                continue
            p[find(u)] = find(v)
            res += w
            n -= 1
            if n == 0:
                break
        return res

All Problems

All Solutions