# 1168.Optimize-Water-Distribution-in-a-Village

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/optimize-water-distribution-in-a-village/

## ้ข็ฎๆ่ฟฐ

``````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 <= 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]``````

## ไปฃ็ 

### Approach #1 Union-Find

Time: O(1) && Space: O(1)

``````class Solution {
class UnionFind {
int[] parent;

public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

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

public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py)        return;

parent[px] = py;
}
}

public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
UnionFind uf = new UnionFind(n + 1);

List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
edges.add(new int[]{0, i + 1, wells[i]});
}

for (int[] pipe: pipes) {
}

Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

int res = 0;
for (int[] edge: edges) {
int x = edge[0];
int y = edge[1];
if (uf.find(x) == uf.find(y))
continue;

uf.union(x, y);
res += edge[2];
}

return res;
}
}``````

Last updated