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 - 1] (note the -1 due to 0-indexing), 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[j] = [house1j, house2j, costj] represents the cost to connect house1j and house2j together using a pipe. Connections are bidirectional, and there could be multiple valid connections between the same two houses with different costs.

Return the minimum total cost to supply water to all houses.

Here 2 sets are mentioned: 1) cost of vertex. 2) cost of edge between vertex1 and vertex2.
Solution is to select either of the node from these sets for each corresponding vertex to get minimum cost. Connect all the vertices with the minimum selected cost.

For this problem, following 2 additional points to be taken care when compared to other simple disjoint set problems:

  • Make one virtual vertex and connect each well with this virtual vertex with the digging cost.
  • combine the above set with the pipes set.
  • sort this combined set using the costs as ascending order.

Then form a disjoint set with this new combined set taking each node beginning from the least cost. If the vertices of a given record in the set are already connected, ignore it. If connected, then add that record cost to the total cost.

Please make your comments.




Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store