LEETCODE 1168. Optimize Water Distribution in a Village 解题思路分析

题目大意：

水资源分配优化

村庄内有n户人家，我们可以通过挖井或者建造水管向每家供水。

对于每户人家i，我们可以通过花费 wells[i] 直接在其房内挖水井，或者通过水管连接到其他的水井。每两户住户间铺设水管的费用通过 pipes 数组表示。 pipes[i] = [house1, house2, cost] 表示住户1到住户2间铺设水管的费用为cost。

请求出所有住户都能通水的最小花费。

示例1：

输入: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出: 3
解释: 
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.

提示：

• 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]

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1168

解题思路分析：

这道题出的很巧妙。我开始想使用动态规划来做，但没想到思路。看了提示才发现原来是Union-Find并查集问题。

我们将所有住户想象成n个节点，如果能将n个节点都连接起来，并且保证至少一家挖了水井，就可使得所有住户都有水喝。不过题目要求找到最优连接方案，也就是要知道如何连接节点，以及挖几口井的总花费最少。我们先来想第一个问题，比如住户A通过某条水管路线通上了水，住户B也通过某条水管通上了水，那么A和B之间是不需要再进行连线的，否则会花费多余的费用。这样一来，所有连线就不会产生回路，也就是说，最终将所有节点接起来之后，应该是一个树形结构。不过问题来了，题目给出的pipes 数组貌似并不足以让所有节点都能保证联通，也就是说，最后可能会形成多棵树，每棵树的顶点是挖井的住户。那么，这多棵树有没有同一个根节点呢？

答案是有！我们忽略了另外一个节点，即水源。本题，我们可以将水源看做是树的根节点，水源到每一个住户的花费为题目给出的 wells数组。wells 数组的长度为n，即每一家理论上都可以联通到水源。因此通过题目给出的条件我们可以得到以下数量的连线：

int lineCount = wells.length + pipes.length;

通过以上的这些条连线一定可以将所有节点以树形结构连接起来，接下来问题就转化为通过已知节点间cost，如果构建一棵总cost最小的树。

我们将所有连线按照cost由小到大排序，然后循环遍历每一条连线，如果连线上两点已经存在相同的根节点，为了避免回路，他们之间不需要连接。反之，两点间需要连接，并将连接cost加入返回结果。直到循环结束算出总cost即是返回结果。因为数组已经排序过，所以可以保证结果为最优。

最后，判断是否具有相同的根节点，只需要利用Union-find并查集即可。

实现代码：

int[] root;
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
    root=new int[n+1]; // 并查集数组
    for(int i=0;i<n+1;i++) root[i]=i; // 初始时每个节点的根节点为自己
    // 存储所有的边
    int[][] allPipes = new int[pipes.length+wells.length][3];
    // 将每户与水源的连线加入allPipes数组
    for(int i=0;i<n;i++){
        allPipes[i]=new int[]{0, i+1, wells[i]};
    }
    // 将每户间的连线加入allPipes数组
    for(int i=n;i<allPipes.length;i++){
        allPipes[i]=pipes[i-n];
    }
    // 按照cost升序排序
    Arrays.sort(allPipes,(x,y)->x[2]-y[2]);
    int res=0; // 返回结果
    for(int[] p : allPipes){
        int r0=root(p[0]); // 连线上第一个节点的根节点
        int r1=root(p[1]); // 连线上第二个节点的根节点
        if(r0==r1) continue; // 根节点相同，不需此连线
        // 以下均为不在同一根节点下的情况

        // 某一个点的根节点为水源
        if(r0==0 || r1==0){
            // 将另一节点也加到根节点下（Union合并操作）
            root[r0]=0;
            root[r1]=0;
        } else{
            // 将一个根节点加入到另一个根节点下（Union合并操作）
            root[r1]=r0;
        }
        res+=p[2]; // 将当前连线cost加入返回结果
    }
    return res;
}
int root(int i){ // 查找根节点
    while(root[i]!=i) i=root[i];
    return i;
}

本题解法执行时间为29ms。

Runtime: 29 ms, faster than 87.65% of Java online submissions for Optimize Water Distribution in a Village.

Memory Usage: 55.8 MB, less than 100.00% of Java online submissions for Optimize Water Distribution in a Village.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1168-optimize-water-distribution-in-a-village-解题思路分析/