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

## 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)

```java
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) {
      edges.add(pipe);
    }

    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;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/union-find/1168.optimize-water-distribution-in-a-village.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.