Optimize Water Distribution in a Village

Jyothi
2 min readMay 1, 2022

--

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.

int findDJ(int *rt, int x){
int rx = rt[x];
if (rx ==x) return x;
return rt[x] = findDJ(rt, rx);
}
int unionDJ(int *rt, int *rnk, int x, int y){
int rx = findDJ(rt, x);
int ry = findDJ(rt, y);
/* if already connected, return 0 */
if (rx == ry)
return 0;
if (rnk[rx] > rnk[ry])
rt[ry] = rx;
else if (rnk[ry] > rnk[rx])
rt[rx] = ry;
else /* both having same rank */{
rt[ry] = rx;
rnk[rx] +=1;
}
return 1; /* as we connected */
}
struct edge{
int v1, v2, cost;
};
int cmp_func(void *arg1, void *arg2){
struct edge *inst1 = (struct edge *)arg1;
struct edge *inst2 = (struct edge *) arg2;
return (inst1->cost - inst2->cost);
}
int minCostToSupplyWater(int n, int* wells, int wellsSize, int** pipes, int pipesSize, int* pipesColSize){
struct edge g[n+1+pipesSize];
int rt[n+1], rnk[n+1], ii;

for (ii=0; ii<wellsSize; ii++){
g[ii].v1 = 0;
g[ii].v2 = ii+1;
g[ii].cost = wells[ii];
}
int jj = ii;
for (ii=0; ii<pipesSize; ii++){
g[jj].v1 = pipes[ii][0];
g[jj].v2 = pipes[ii][1];
g[jj++].cost = pipes[ii][2];
}
qsort(g, jj, sizeof(struct edge), cmp_func);
for (ii=0; ii<n+1; ii++){
rt[ii] = ii;
rnk[ii] = 0;
}

int totcost = 0;
/* form a a graph */
for (ii=0; ii<jj; ii++){
/* if 2 vertices are connected successfully, increase total cost */
if (unionDJ(rt, rnk, g[ii].v1, g[ii].v2))
{
totcost += g[ii].cost;
}
}

return totcost;
}

Please make your comments.

--

--