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)

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