Leetcode 1168:水资源分配优化(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1168:水资源分配优化(超详细的解法!!!)

in leetcode with 0 comment

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i,我们有两种可选的供水方案:

请你帮忙计算为所有房子都供水的最低总成本。

示例:

输入:n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出:3
解释: 
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井(成本为 1),然后将其他房子铺设管道连起来(成本为 2),所以总成本为 3。

提示:

解题思路

首先不难看出这是一个最小生成树的问题,可以参看这篇最小生成树(超详细!!!)。但是我们仔细观察题目,题目给我们的边(pipes)不够怎么办?也就是没法形成最小生成树。那么我们就需要加边,怎么加?我们的wells没用呢!我们可以定义一个0号房子,0号房子到其他房子的成本就是wells数组中的值。

这个问题的代码和Leetcode 1135:最低成本联通所有城市(超详细的解法!!!)类似

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        for i, v in enumerate(wells):
            pipes.append([0, i+1, v])
        
        pipes.sort(key=lambda x:x[2])
        parents = [i for i in range(n + 1)]
        
        def find(x):
            if x != parents[x]:
                parents[x] = find(parents[x])
            return parents[x]
        
        res, e, k = 0, 0, 0
        while e < n:
            u, v, w = pipes[k]
            k += 1
            x, y = find(u), find(v)
            if x != y:
                e += 1
                res += w
                parents[x] = y
        return res

非常的轻松加愉快!

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses