用 Python 优化村庄的水分配

pythonserver side programmingprogramming更新于 2025/8/6 3:56:17

假设村庄里有 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

相关文章


有用资源