1168 - Optimize Water Distribution in a Village
Dibyabrata Panja
2824
Graph TheoryInterview

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:
image

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]

Submission link for non-premium members:
https://www.codingninjas.com/codestudio/problems/water-supply-in-a-village_1380956?leftPanelTab=0

class DSU
    {
        public:
        int *par,*size;
        DSU(int n)
        {
            par=new int[n+2];
            size=new int[n+2];
            
            for(int i=0;i<n+2;i++)
            {
                par[i]=i;
                size[i]=1;
            }
        }
            
            int find(int x)
            {
                if(x==par[x])
                    return x;
                return par[x]=find(par[x]);
            }
            
            bool join(int a,int b)
            {
                int pa=find(a);
                int pb=find(b);
                
                if(pa==pb)
                    return 1;
                
                if(size[pa]<=size[pb])
                {
                    par[pa]=pb;
                    size[pb]+=size[pa];
                }
                else
                {
                    par[pb]=pa;
                    size[pa]+=size[pb];
                }
                
                return 0;
            }
    };

int supplyWater(int n, int k, vector<int> &wells, vector<vector<int>> &pipes)
{
  	DSU dsu(n);
    priority_queue<pair<int,pair<int,int>>>pQ;
    
    //Take a dummy node for the well,we need to consider the well as a node
	//here point (n+1) represents the well  
	//as the houses are numbered from 1 choosing 0 to represent the well would have been a better choice.
	//MANIPULATE THE DSU AS PER YOUR CHOCE.
    for(int i=1;i<=n;i++)
    {
        pQ.push({-wells[i-1],{i,n+1}});
    }
    
    for(auto &p:pipes)
    {
        pQ.push({-p[2],{p[0],p[1]}});
    }
    
    int min_cost=0,tot_connections=0;
    while(!pQ.empty())
    {
        //for a MST containing n+1 nodes(considering well too) we need n connections
        if(tot_connections==n)
            return min_cost;
        
        auto [cost,P]=pQ.top();
        auto [u,v]=P;
        pQ.pop();
        
        cost*=-1;
        
        //if there is no connection yet between u and v add that to the cost
        //and increase the connection count
        if(!dsu.join(u,v))
        {min_cost+=cost;tot_connections++;}
        
    }
    
    return min_cost;
}
Comments (3)