用 Python 优化村庄的水分配
假设村庄里有 n 栋房子。我们必须通过建造水井和铺设管道为所有房屋供水。对于每栋房子 i,我们可以在里面建造一口水井,建筑成本为 wells[i],或者从另一口水井将水引到它。在房屋之间铺设管道的成本由数组 pipes 给出,其中每个 pipes[i] 为 [house1, house2, cost],表示使用管道将 house1 和 house2 连接在一起的成本。这些连接是双向的。我们必须找到为所有房屋供水的最低总成本。
因此,如果输入为 n = 3、水井 = [1,2,2]、管道 = [[1,2,1],[2,3,1]],则输出将为 3

如上图所示,显示了使用管道连接房屋的成本。最好的策略是在第一栋房子里建一口水井,成本为 1,然后以成本 2 将其他房屋连接到该水井,因此总成本为 3。
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数 find()。这将需要一个
如果 parent[a] 与 -1 相同,则
返回 a
parent[a] := find(parent[a])
返回 parent[a]
定义一个函数 union()。这将需要 a,b
parent_a := find(a)
parent_b := find(b)
如果 parent_a 与 parent_b 相同,则
返回 True
parent[parent_b] := parent_a
返回 False
从主方法执行以下操作 −
parent := 制作一个大小为 n + 1 的列表,用 -1 填充
counter := 0
对于 i,范围为 0 到大小为 well,执行
在管道末尾插入 [0, i+1, well[i]]
counter := counter + 1
根据成本对管道数组进行排序
cost := 0
对于管道中的每个 i,执行
source := i[0]
destination := i[1]
temp := i[2]
如果 union(source,destination) 为 false,则
cost := cost +临时
返回 cost
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object): def find(self, a): if self.parent[a] == -1: return a self.parent[a] = self.find(self.parent[a]) return self.parent[a] def union(self,a,b): parent_a = self.find(a) parent_b = self.find(b) if parent_a == parent_b: return True self.parent[parent_b] = parent_a return False def minCostToSupplyWater(self, n, well, pipes): self.parent = [-1 for i in range(n+1)] counter = 0 for i in range(len(well)): pipes.append([0,i+1,well[i]]) counter+=1 pipes = sorted(pipes,key=lambda v:v[2]) cost = 0 for i in pipes: #print(i) source = i[0] destination = i[1] temp = i[2] if not self.union(source,destination): cost+=temp return cost ob = Solution() print(ob.minCostToSupplyWater(3, [1,2,2], [[1,2,1],[2,3,1]]))
输入
3, [1,2,2], [[1,2,1],[2,3,1]]
输出
1
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

