# 1168.optimize-water-distribution-in-a-village-en

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]

example 1 pic:

example 1

From example graph, we can see that this is Shortest path problem/Minimum spanning tree problem. In this problem, in a graph, view cities as nodes, pipe connects two cities as edges with cost. here, wells costs, it is self connected edge, we can add extra node as root node

`0`

, and connect all `0`

and `i`

with costs `wells[i]`

. So that we can have one graph/tree, and how to get minimun spanning trees / shortest path problem in a graph. Please see below detailed steps for analysis.Analysis Steps：

- 1.Create
`POJO EdgeCost(node1, node2, cost) - node1, node2, and cost of connect node1 and node2`

- 2.Assume on
`root node 0`

，build graph with`node 0 and all nodes(cities)`

- 3.Connect all nodes with
`0`

，`[0,i] - i is nodes range from [1,n]`

，`0-1`

meaning`node 0`

and`node 1`

connect edge ，value is node`i`

's cost`wells[i]`

; - 4.Turn cities into nodes, wells' costs and pipes' into costs into edges value which connected into two cities.
- 5.Sort all edges (from min to max)
- 6.Scan all edges, check whether 2 nodes connected or not:（
`Union-Find`

），- if already connected, continue check next edge
- if not yet connected, +costs, connect 2 nodes

- 7.If all nodes already connected, get minimum costs, return result
- 8.(#7 Optimization) for each
`union`

, total nodes number`n-1`

, if`n==0`

, then meaning all nodes already connected, can terminate early.

Here use weighted-Union-find to check whether 2 nodes connceted or not, and union not connected nodes.

For example：

`n = 5, wells=[1,2,2,3,2], pipes=[[1,2,1],[2,3,1],[4,5,7]]`

As below pic:

minimum cost

From above pictures, we can see that all nodes already connected with minimum costs.

*Time Complexity:*`O(ElogE) - E number of edge in graph`

*Space Complexity:*`O(E)`

- 1.Build graph with all possible edges.
- 2.Sort edges by value (costs)
- 3.Iterate all edges (from min value to max value)
- 4.For each edges, check whether two nodes already connected (union-find),
- if already connected, then skip
- if not connected, then union two nodes, add costs to result

*Java code*

class OptimizeWaterDistribution {

public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {

List<EdgeCost> costs = new ArrayList<>();

for (int i = 1; i <= n; i++) {

costs.add(new EdgeCost(0, i, wells[i - 1]));

}

for (int[] p : pipes) {

costs.add(new EdgeCost(p[0], p[1], p[2]));

}

Collections.sort(costs);

int minCosts = 0;

UnionFind uf = new UnionFind(n);

for (EdgeCost edge : costs) {

int rootX = uf.find(edge.node1);

int rootY = uf.find(edge.node2);

if (rootX == rootY) continue;

minCosts += edge.cost;

uf.union(edge.node1, edge.node2);

// for each union, we connnect one node

n--;

// if all nodes already connected, terminate early

if (n == 0) {

return minCosts;

}

}

return minCosts;

}

class EdgeCost implements Comparable<EdgeCost> {

int node1;

int node2;

int cost;

public EdgeCost(int node1, int node2, int cost) {

this.node1 = node1;

this.node2 = node2;

this.cost = cost;

}

@Override

public int compareTo(EdgeCost o) {

return this.cost - o.cost;

}

}

class UnionFind {

int[] parent;

int[] rank;

public UnionFind(int n) {

parent = new int[n + 1];

for (int i = 0; i <= n; i++) {

parent[i] = i;

}

rank = new int[n + 1];

}

public int find(int x) {

return x == parent[x] ? x : find(parent[x]);

}

public void union(int x, int y) {

int px = find(x);

int py = find(y);

if (px == py) return;

if (rank[px] >= rank[py]) {

parent[py] = px;

rank[px] += rank[py];

} else {

parent[px] = py;

rank[py] += rank[px];

}

}

}

}

*Pythong3 code*

class Solution:

def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:

union_find = {i: i for i in range(n + 1)}

def find(x):

return x if x == union_find[x] else find(union_find[x])

def union(x, y):

px = find(x)

py = find(y)

union_find[px] = py

graph_wells = [[cost, 0, i] for i, cost in enumerate(wells, 1)]

graph_pipes = [[cost, i, j] for i, j, cost in pipes]

min_costs = 0

for cost, x, y in sorted(graph_wells + graph_pipes):

if find(x) == find(y):

continue

union(x, y)

min_costs += cost

n -= 1

if n == 0:

return min_costs