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

Problem

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

Problem 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 <= 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:

Solution

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 with0，[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:

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

Complexity Analysis

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

• Space Complexity: O(E)

A graph at most have n(n-1)/2 - n number of nodes in graph edges （Complete Graph）

Key Points

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

Code (Java/Python3)

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

External Resources

1. Shortest path problem

2. Dijkstra's algorithm

3. Floyd–Warshall algorithm

4. Bellman–Ford algorithm

5. Kruskal's algorithm

6. Prim's algorithm

7. Minimum spanning tree