使用Python优化乡村水资源分配

假设一个村庄有n户人家。我们需要通过建造水井和铺设管道为所有房屋供水。对于每户人家i，我们可以选择在其内部建造一口井，建造成本为wells[i]，或者从另一口水井向其铺设管道。房屋之间铺设管道的成本由数组pipes给出，其中每个pipes[i]为[house1, house2, cost]，表示连接house1和house2的成本。这些连接是双向的。我们需要找到为所有房屋供水的最小总成本。

因此，如果输入类似于n = 3，wells = [1,2,2]，pipes = [[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

  • 对于从0到well大小的范围内的i，执行以下操作：

    • 在pipes的末尾插入[0, i+1, well[i]]

    • counter := counter + 1

  • 根据成本对pipes数组进行排序

  • cost := 0

  • 对于pipes中的每个i，执行以下操作：

    • source := i[0]

    • destination := i[1]

    • temp := i[2]

    • 如果union(source,destination)为false，则

      • cost := cost + temp

  • 返回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

更新于：2020年7月11日

582 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告