เพิ่มประสิทธิภาพการจ่ายน้ำในหมู่บ้านใน Python

สมมุติว่าในหมู่บ้านมีบ้าน n หลัง เราต้องจัดหาน้ำสำหรับบ้านทุกหลังด้วยการสร้างบ่อน้ำและวางท่อ สำหรับบ้านแต่ละหลัง i เราสามารถสร้างบ่อน้ำในนั้นได้ ค่าก่อสร้างจะเป็นบ่อน้ำ[i] หรือวางท่อน้ำจากบ่ออื่นเข้าไป ค่าใช้จ่ายในการวางท่อระหว่างบ้านจะได้รับจากท่ออาร์เรย์ โดยที่ท่อแต่ละท่อ[i] คือ [บ้าน1 บ้าน2 ต้นทุน] แสดงถึงต้นทุนในการเชื่อมต่อบ้าน1และบ้าน2เข้าด้วยกันโดยใช้ท่อ การเชื่อมต่อเหล่านี้เป็นแบบสองทิศทาง เราต้องหาต้นทุนรวมขั้นต่ำในการจัดหาน้ำให้บ้านทุกหลัง

ดังนั้น หากอินพุตเป็น n =3, wells =[1,2,2], pipes =[[1,2,1],[2,3,1]] ผลลัพธ์จะเป็น 3

จากภาพด้านบนแสดงต้นทุนการต่อบ้านโดยใช้ท่อ กลยุทธ์ที่ดีที่สุดคือสร้างบ่อน้ำในบ้านหลังแรกด้วยราคา 1 และเชื่อมต่อบ้านหลังอื่นด้วยราคา 2 ดังนั้นราคาทั้งหมดจึงเท่ากับ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน find() นี่จะใช้เวลา

• ถ้า parent[a] เหมือนกับ -1 แล้ว

  • กลับ

• parent[a] :=find(parent[a])

• ส่งคืนพาเรนต์[a]

• กำหนดฟังก์ชัน union() นี่จะใช้เวลา a,b

• parent_a :=find(a)

• parent_b :=find(b)

• ถ้า parent_a เหมือนกับ parent_b แล้ว

  • คืนค่า True

• parent[parent_b] :=parent_a

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• parent :=ทำรายการขนาด n + 1 เติมด้วย -1

• เคาน์เตอร์ :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของดีทำ

  • ใส่ [0, i+1, well[i]] ที่ปลายท่อ

  • เคาน์เตอร์ :=เคาน์เตอร์ + 1

• จัดเรียงท่ออาร์เรย์ตามต้นทุน

• ราคา :=0

• สำหรับแต่ละฉันในท่อทำ

  • ที่มา :=i[0]

  • ปลายทาง :=i[1]

  • อุณหภูมิ :=i[2]

  • หากสหภาพ (ต้นทาง, ปลายทาง) เป็นเท็จ

    • ราคา :=ต้นทุน + อุณหภูมิ

• ค่าส่งคืน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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