> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/optimize-water-distribution-in-a-village.md).

# Optimize Water Distribution in a Village

There are N homes in a village, we have to facilitate water supply in each of them. We can either build a well in a home or connect it with pipe to some different home already having water supply. More formally, we can either build a new well in the home or connect it with a pipeline to some different home which either has it’s own well or further gets water supply from a different home and so on. There is some cost associated with both building a new well and laying down a new pipeline. We have to supply water in all homes and minimise the total cost.

Input-\
First line contains an integer N, the number of homes.\
The next line contains N integers, the ith integer denotes the cost of building a well in that home.\
Next line contains an integer K, then K lines follows. Each of which contains 3 integers i, j and p. Which denotes the cost ‘p’ of laying down pipeline between homes i and j.

Output-\
Output a single integer - the minimum cost to supply water to all the homes

```java
class solution {
    public static int findParent(int[] parent, int n) {
        while (parent[n] != n)
            n = parent[n];
        return n;
    }

    public static int findMinCost(int n, int[][] edges, int[] wells) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        for (int[] edge : edges)
            pq.add(edge);
        // Dummy edges from wells
        for (int i = 0; i < n; i++)
            pq.add(new int[] { n, i, wells[i] });
        // Parent Array
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        int minCost = 0;
        // This will make exactly n edges
        // Because we added 1 dummy node
        // therefore total nodes -> n+1
        // number of edges such that all receive water -> n
        while (pq.size() > 0) {
            int[] edge = pq.poll();
            int parentX = findParent(parent, edge[0]);
            parent[edge[0]] = parentX;
            int parentY = findParent(parent, edge[1]);
            parent[edge[1]] = parentY;
            if (parentX != parentY) {
                parent[parentX] = parentY;
                minCost += edge[2];
            }
        }
        return minCost;
    }
}
```