Vultr DocsLatest Content

Optimize Water Distribution in a Village

Updated on 10 July, 2025
Optimize Water Distribution in a Village header image

Problem Statement

In a certain village made up of n houses, there is a need to facilitate each house with a water supply. To achieve this, one can install water wells directly inside each house or connect the houses using pipes to share water from an existing well in another house. Each option comes with a cost: building a well in a house i costs wells[i-1] (accounting for 0-indexing), and connecting two houses house1j and house2j via a pipeline carries a specific cost costj as denoted in the pipes array where pipes[j] = [house1j, house2j, costj]. These pipe connections are bidirectional, meaning water can flow either way once the connection is made, and there could be several different costs available to connect the same two houses. The primary goal is to find a strategy that results in providing water to all houses while incurring the minimum total cost.

Examples

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.

Example 2

Input:

n = 2, wells = [1,1], pipes = [[1,2,1],[1,2,2]]

Output:

2

Explanation:

We can supply water with cost two using one of the three options:
Option 1:
- Build a well inside house 1 with cost 1.
- Build a well inside house 2 with cost 1.
The total cost will be 2.
Option 2:
- Build a well inside house 1 with cost 1.
- Connect house 2 with house 1 with cost 1.
The total cost will be 2.
Option 3:
- Build a well inside house 2 with cost 1.
- Connect house 1 with house 2 with cost 1.
The total cost will be 2.
  
Note that we can connect houses 1 and 2 with cost 1 or with cost 2 but we will always choose the cheapest option.

Constraints

  • 2 <= n <= 104
  • wells.length == n
  • 0 <= wells[i] <= 105
  • 1 <= pipes.length <= 104
  • pipes[j].length == 3
  • 1 <= house1j, house2j <= n
  • 0 <= costj <= 105
  • house1j != house2j

Approach and Intuition

To determine the minimum cost to supply water using either wells or pipes, consider the following strategic steps:

  1. Recognize that each house having its own well is a straightforward but potentially expensive solution. It’s a base case where each house is handled independently without any cost-saving benefits from pipe connections.

  2. Identify that connections between houses potentially offer cost-saving synergies. If the cost to connect two houses is less than installing separate wells in each, then using a pipe is more advantageous.

  3. The problem, therefore, revolves around evaluating all possible combinations of wells and pipes to ensure all houses are connected directly or indirectly to a water source at the lowest cost. This becomes a typical graph problem where houses are nodes, and pipes are edges with weights determined by connection costs.

  4. The aim is to form a Minimum Spanning Tree (MST) of the village where the source of water (either a well or a pipe) is used in an optimized way to connect all houses. The MST model ensures that all houses (nodes) are connected with the minimum total edge (pipe costs) weight, potentially augmented with well costs if they're cheaper.

  5. Utilize graph algorithms like Kruskal's or Prim's, which are suited for finding the MST of a graph. To adapt these algorithms:

    • Include wells as edges by contemplating a virtual node representing an external water source connected to each house with an edge weighted by the well’s cost. This turns the problem into a classic MST problem where you select edges (either the well or a pipe) to ensure all nodes are connected at the lowest total cost.

  6. Implement and iterate through these algorithms to ensure each decision (to lay a pipe or build a well) reflects the minimal cost approach as influenced by the current state of connected houses.

In summary, the approach revolves around utilizing graph theory, specifically MST, to judiciously decide between building new wells or laying pipes to connect existing ones, ensuring every house gets water at the least possible cost. By dynamically adjusting the decisions as more houses get connected, one can find the optimal configuration of wells and pipes that meets the required conditions.

Solutions

  • Java
java 
class DisjointSet {
    private int[] parent;
    private int[] height;
    
    public DisjointSet(int count) {
        parent = new int[count + 1];
        height = new int[count + 1];
        for (int i = 0; i <= count; ++i) {
            parent[i] = i;
            height[i] = 0;
        }
    }
    
    public int locate(int member) {
        if (parent[member] != member) {
            parent[member] = locate(parent[member]);
        }
        return parent[member];
    }
    
    public boolean merge(int elem1, int elem2) {
        int root1 = locate(elem1);
        int root2 = locate(elem2);
        if (root1 == root2) {
            return false;
        }
    
        if (height[root1] > height[root2]) {
            parent[root2] = root1;
        } else if (height[root1] < height[root2]) {
            parent[root1] = root2;
        } else {
            parent[root1] = root2;
            height[root2] += 1;
        }
    
        return true;
    }
}
    
    
class WaterSupplyOptimizer {
    public int minimumCostToProvideWater(int n, int[] wellCosts, int[][] connections) {
        List<int[]> edges = new ArrayList<>(n + 1 + connections.length);
    
        for (int i = 0; i < wellCosts.length; ++i) {
            edges.add(new int[]{0, i + 1, wellCosts[i]});
        }
    
        for (int[] connection : connections) {
            edges.add(connection);
        }
    
        Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
    
        DisjointSet ds = new DisjointSet(n);
        int cost = 0;
        for (int[] edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            int weight = edge[2];
            if (ds.merge(node1, node2)) {
                cost += weight;
            }
        }
    
        return cost;
    }
}

To optimize water distribution in a village using Java, an efficient approach involves utilizing Kruskal's algorithm combined with a union-find (or disjoint set) data structure. Below is the breakdown of how the solution is implemented:

  • DisjointSet Class:

    • Variables: Two arrays, parent and height, maintain each element’s parent and tree height, respectively.
    • Constructor (DisjointSet(int count)): Initializes the arrays, setting each element to be its own parent and its tree height to zero.
    • locate(int member) Method: Finds the root of the member, employing path compression to flatten the structure which speeds up subsequent queries.
    • merge(int elem1, int elem2) Method: Joins two subsets, including union by height logic to maintain a more balanced tree, reducing the time complexity of future operations.

  • WaterSupplyOptimizer Class:

    • minimumCostToProvideWater(int n, int[] wellCosts, int[][] connections) Method:
      • Begins with listing all edges that represent potential connections, including direct well connections by linking node 0 (imaginary super node for wells) to actual nodes (i + 1) alongside respective wellCosts.
      • Adds existing village connections as edges.
      • Sorts these edges based on weight (cost) to prepare for Kruskal’s algorithm which ensures minimum spanning tree is created using the smallest weight edges.
      • An instance of DisjointSet is created to track and manage disjoint sets.
      • For each sorted edge, tries to merge nodes. If successful (nodes were in distinct sets), adds the edge’s weight to the total cost.

The efficient management of union-find operations ensures an almost linear time complexity operation on average per edge processed. The algorithm consistently checks minimal edges first, ensuring the minimum cost to provide water to all nodes (houses) in the village.

  • Python
python 
class DisjointSet:
    def __init__(self, size) -> None:
        self.parent = [i for i in range(size + 1)]
        self.height = [0] * (size + 1)
        
    def find_parent(self, member: int) -> int:
        if self.parent[member] != member:
            self.parent[member] = self.find_parent(self.parent[member])
        return self.parent[member]
    
    def connect(self, member_a: int, member_b: int) -> bool:
        root_a = self.find_parent(member_a)
        root_b = self.find_parent(member_b)
    
        if root_a == root_b:
            return False
    
        if self.height[root_a] > self.height[root_b]:
            self.parent[root_b] = root_a
        elif self.height[root_a] < self.height[root_b]:
            self.parent[root_a] = root_b
        else:
            self.parent[root_a] = root_b
            self.height[root_b] += 1
    
        return True
    
class WaterNetworkSolution:
    def calculateMinimumCost(self, n: int, well_costs: List[int], connections: List[List[int]]) -> int:
        possible_links = []
    
        for idx, cost in enumerate(well_costs):
            possible_links.append((cost, 0, idx+1))
    
        for house1, house2, cost in connections:
            possible_links.append((cost, house1, house2))
            
        possible_links.sort(key=lambda x: x[0])
    
        ds = DisjointSet(n)
        min_total_cost = 0
            
        for cost, house1, house2 in possible_links:
            if ds.connect(house1, house2):
                min_total_cost += cost
    
        return min_total_cost

This Python solution for optimizing water distribution in a village uses a Disjoint Set (Union-Find) data structure combined with a greedy approach implementing Kruskal’s Minimum Spanning Tree algorithm.

  • The DisjointSet class facilitates managing connections between elements (houses, in this context), including:

    • Initializing a standard parent list where each element is its own parent.
    • Dynamically linking sets with the connect method which merges two sets and possibly increases the height to balance the structure for efficient future operations.
    • Finding the optimal root of a set using path compression in the find_parent method, reducing the effective depth of trees during searches.

  • The WaterNetworkSolution class contains the calculateMinimumCost method that computes the least total cost to supply water to all houses:

    • First, initializes a list of potential water links, both direct well installations at each house and the given inter-house connections.
    • Stores these as tupled entries (cost, from-house, to-house) including a zero-indexed from-house for well costs to simulate them as edge connections from a virtual house 0.
    • Sorts these links by cost to set up for a greedy selection—picking the least expensive options first, ensuring effective distribution.
    • Iterates over sorted links, using the DisjointSet to only add connections if they help in connecting more houses without forming cycles, thus maintaining a growing spanning tree.
    • The total cost accumulates with each successfully established link until all houses are interconnected either directly or indirectly.

Finally, this method returns the cumulative minimum cost after efficiently interconnecting all necessary components. This solution effectively ensures that every house gets water at the minimal possible expense by handling both direct well costs and potential shared connections.

Comments

No comments yet.