Tối ưu hóa việc phân phối nước trong một ngôi làng bằng Python

Giả sử có n ngôi nhà trong một ngôi làng. Chúng tôi phải cung cấp nước cho tất cả các ngôi nhà bằng cách xây giếng và đặt đường ống. Đối với mỗi ngôi nhà i, chúng ta có thể xây một cái giếng bên trong nó, chi phí xây dựng sẽ là cái giếng [i], hoặc đường ống dẫn nước từ giếng khác đến nó. Chi phí để đặt các đường ống giữa các ngôi nhà được đưa ra bởi các đường ống mảng, trong đó mỗi đường ống [i] là [house1, house2, cost] đại diện cho chi phí để kết nối house1 và house2 với nhau bằng cách sử dụng một đường ống. Các kết nối này là hai chiều. Chúng tôi phải tìm tổng chi phí tối thiểu để cung cấp nước cho tất cả các ngôi nhà.

Vì vậy, nếu đầu vào là n =3, well =[1,2,2], pipe =[[1,2,1], [2,3,1]], thì đầu ra sẽ là 3

như từ hình ảnh trên cho thấy chi phí của việc kết nối các ngôi nhà bằng cách sử dụng đường ống. Chiến lược tốt nhất sẽ là xây một cái giếng ở ngôi nhà đầu tiên với chi phí 1 và nối những ngôi nhà khác với nó với chi phí 2 để tổng chi phí là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm find (). Điều này sẽ mất một
nếu cha [a] giống -1 thì
- trả lại một
cha [a]:=find (cha [a])
trả về cha mẹ [a]
Định nghĩa một hàm union (). Điều này sẽ mất a, b
parent_a:=find (a)
parent_b:=find (b)
nếu parent_a giống như parent_b, thì
- trả về True
cha mẹ [parent_b]:=parent_a
trả về Sai
Từ phương thức chính, hãy làm như sau -
cha:=tạo một danh sách có kích thước n + 1, điền vào giá trị này bằng -1
bộ đếm:=0
đối với tôi trong phạm vi từ 0 đến kích thước của tốt, hãy làm
- chèn [0, i + 1, well [i]] vào cuối đường ống
- bộ đếm:=bộ đếm + 1
sắp xếp mảng đường ống dựa trên chi phí
chi phí:=0
đối với mỗi tôi trong đường ống, hãy thực hiện
- nguồn:=i [0]
- đích:=i [1]
- tạm thời:=i [2]
- nếu union (nguồn, đích) là false, thì
  - chi phí:=chi phí + tạm thời
chi phí trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

3, [1,2,2], [[1,2,1],[2,3,1]]

Tối ưu hóa việc phân phối nước trong một ngôi làng bằng Python

Ví dụ

Đầu vào

Đầu ra