Last Updated: 2 Apr, 2021

Water Supply In A Village

Hard

Asked in companies

Solve now

Problem statement

There are ‘N’ houses in a village. Ninja wants 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 total cost to lay pipes between houses is given by the array ‘PIPES’, where ‘PIPES[i]’ = ‘[HOUSE1, HOUSE2, COST]’ and the ‘COST’ represent the total cost connect ‘HOUSE1’ and ‘HOUSE2’ together using a pipe.

Note: Given all the connections are bidirectional.

For Example:

For ‘N’ = 3, ‘WELLS[]’ = ‘[1,2,2]’, ‘PIPES[]’ = [ [1, 2, 1], [2 , 3, 1]]. 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.

Ninja wants to find out the minimum total cost to supply water to all houses in the village. Can you help the Ninja to find out this minimum cost?

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘K’ representing the number of Houses in the village and the size of ‘PIPES’ respectively.

The next line contains ‘N’ single space-separated integers denoting ‘WELLS[i]’.

The next ‘K’ line contains 3 single space-separated integers denoting ‘PIPES[i][0]’, ‘PIPES[i][1]’ and ‘PIPES[i][2]’.

Output Format :

For each test case, print the minimum cost to supply water to all the houses in the village. 

The output for each test case is printed in a separate line.

Constraints :

1 <= T <= 100
1 <= N <= 10 ^ 2
0 <= WELLS[i] <= 10^5
1 <= K <= 10000
1 <= PIPES[i][0], PIPES[i][1] <= N
0 <= PIPES[i][2] <= 10^5
PIPES[i][0] != PIPES[i][1]

Where ‘T’ is the number of test cases, ‘N’ is the number of houses in the village, WELL[i]’ denotes the cost of inserting a well at house ‘i’ and ‘PIPES[i][0]’, ‘PIPES[i][1]’ and ‘PIPES[2]’ represents the cost to connect house ‘PIPES[i][0]’ to ‘PIPES[i][1]’.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We can assume this problem as a Shortest path problem/Minimum spanning tree problem. In this problem, in a graph, consider cities as nodes, pipe connects two cities as edges with cost. Now wells cost, they are self-connected edges, we can add an extra node as root node 0, and connect all 0 and every node with costs ‘WELLS[i]’. So that we can have one graph/tree, and can get minimum spanning trees / shortest path in a graph.

Here is the complete algorithm:

Create a helper function ‘edgeCost(house1, house2, cost)’, where ‘cost’ is the cost to connect ‘house1’ and ‘house2’.
Assume ‘0’ as the root node, now build a graph with node 0 and all nodes (Houses).
Connect all nodes with 0 while forming the graph.
Turn houses into nodes well's costs and pipes' cost into edges value which connect into two cities.
Sort all edges (from min to max).
Scan all edges, check whether 2 nodes connected or not:（Union-Find method).
If already connected, continue to check the next edge.
If not yet connected, connect 2 nodes add cost to the final answer.
If all nodes already connected, get minimum costs, return the result.

Solve now

02 Approach

In this approach, we will find the minimum spanning tree of the given graph as a minimum spanning tree of a graph is a subset of the graph that connects all the vertices(houses in this case) with the minimum total cost.

To deal with the cost of Well, we will create an extra node having index 0 and connect all the houses to this node and the edge weight will be WELL[i].

It can be considered that Node 0 is the main supply to all the wells of the kingdom.

After updating the graph and storing it in an adjacency list manner.We will use Prims Algorithm using priority queue to find the cost of minimum spanning tree.

Algorithm:

Defining PRIMS(N, ‘GRAPH’):
- This function will return the total cost of the MST formed for the given ‘GRAPH’ having ‘N’ vertices.
- Declare ‘IN_MST’ array of size ‘N’ that will store whether the vertex is added to the MST or not.
- Declare ‘COST’ array of size ‘N’ that will store the cost of adding the vertex to the MST.
- Declare a priority queue ‘PQ’ that will extract the minimum weight edge in each step. It will store the values in pairs as (cost, vertex).
- Set all values of ‘IN_MST’ as 0.(No vertex is visited yet.)
- Set all values of ‘COST’ to INF(a large value).
- Start the MST with vertex 0.
- Set ‘COST[0]’ as 0.
- Set ‘IN_MST[0]’ as 1.
- Insert { 0,COST[0] } into priority queue PQ.
- While PQ is not empty:
  - Set ‘CUR’ as vertex of top element of PQ.
  - Pop the top element from the PQ.
  - Set ‘IN_MST[CUR] as 1.
  - For i in GRAPH[‘CUR’]:
    - Set ‘V’ as vertex corresponding to i.
    - Set ‘C’ as cost corresponding to i.
    - If ‘IN_MST’[V] == 0 and COST[V] > C:
      - Found an edge with lesser weight.
      - Set ‘COST[V] ’ as C.
      - Insert {V,COST[‘V’]} into PQ.
- Now,MST is completed.
- Set ‘TOTAL_COST’ as 0.
- Computing the total cost of MST.
- For i in range(N):
  - Set ‘TOTAL_COST’ as ‘TOTAL_COST’ + ‘COST[i]’.
- Return ‘TOTAL_COST’ .

Declare an array of ‘N+1’ dynamic arrays ‘GRAPH’ to store the graph in an adjacency list manner.
For ‘EDGE’ in ‘PIPES’:
- Set i as EDGE[0].
- Set j as EDGE[1].
- Set ‘COST’ as EDGE[2].
- Insert {i,COST} into ‘GRAPH[j]’.
- Insert {j,COST} into ‘GRAPH[i]’.
For i in range 0 to N-1:
- Insert {0,WELL[i]} into GRAPH[i+1].
- Insert {i+1,WELL[i]} into GRAPH[0].
Graph is prepared.
Set ‘COST’ as PRIMS(‘GRAPH’,’N’).
Return ‘COST’

Solve now