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:
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 <= 10000wells.length == n0 <= wells[i] <= 10^51 <= pipes.length <= 100001 <= pipes[i][0], pipes[i][1] <= n0 <= pipes[i][2] <= 10^5pipes[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]; } } ############ 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 -
var p []int func minCostToSupplyWater(n int, wells []int, pipes [][]int) int { p = make([]int, n+1) for i := 0; i < len(p); i++ { p[i] = i } for i, w := range wells { pipes = append(pipes, []int{0, i + 1, w}) } sort.Slice(pipes, func(i, j int) bool { return pipes[i][2] < pipes[j][2] }) res := 0 for _, e := range pipes { 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 } func find(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } -
function minCostToSupplyWater( n: number, wells: number[], pipes: number[][], ): number { for (let i = 0; i < n; ++i) { pipes.push([0, i + 1, wells[i]]); } pipes.sort((a, b) => a[2] - b[2]); const p = new Array(n + 1).fill(0).map((_, i) => i); const find = (x: number): number => { if (p[x] !== x) { p[x] = find(p[x]); } return p[x]; }; let ans = 0; for (const [i, j, c] of pipes) { const pa = find(i); const pb = find(j); if (pa === pb) { continue; } p[pa] = pb; ans += c; if (--n === 0) { break; } } return ans; }