เชื่อมต่อเมืองด้วยต้นทุนขั้นต่ำใน Python

สมมติว่ามี N เมืองที่มีหมายเลขตั้งแต่ 1 ถึง N เรามีการเชื่อมต่อ โดยที่การเชื่อมต่อแต่ละแห่ง [i] คือ [city1, city2, cost] ซึ่งแสดงถึงต้นทุนในการเชื่อมต่อ city1 และ city2 เข้าด้วยกัน . เราต้องหาต้นทุนขั้นต่ำเพื่อให้ทุกเมืองมีเส้นทางเชื่อมต่อ (อาจมีความยาว 1) ที่เชื่อมสองเมืองเข้าด้วยกัน ค่าใช้จ่ายเป็นผลรวมของต้นทุนการเชื่อมต่อที่ใช้ หากภารกิจนี้เป็นไปไม่ได้ ให้คืนค่า -1

ดังนั้นหากกราฟเป็นเช่น −

จากนั้นผลลัพธ์จะเป็น 6 การเลือกสองเมืองใด ๆ จะเชื่อมโยงทุกเมืองดังนั้นเราจึงเลือกขั้นต่ำ 2, [1, 5]

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

• กำหนดวิธีการที่เรียกว่า find() ซึ่งจะใช้เวลา x

• ถ้า parent[x] คือ -1 ให้คืนค่า x

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

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

• สร้างวิธีอื่นที่เรียกว่า union() ซึ่งจะใช้ x และ y

• parent_x :=find(x), parent_y :=find(y)

• ถ้า parent_x =parent_y ให้ส่งคืน มิฉะนั้น parent[parent_y] :=parent_x

• จากวิธีหลัก จะใช้ n และ conn

• parent :=อาร์เรย์ขนาด n และเติมด้วย – 1, ตั้งค่า disjoint :=n – 1, ราคา :=0

• c :=เรียงลำดับรายการของ conn จัดเรียงตามต้นทุน

• ผม :=0

• ในขณะที่ i <ความยาวของ c และ disjoint ไม่ใช่ 0

  • x :=c[i, 0] และ y :=c[i, 1]

  • ถ้า find(x) ไม่เหมือนกับ find(y) ให้ลดการ disjoint ลง 1 ให้เพิ่มราคา c[i, 2] และดำเนินการ union(x, y)

  • เพิ่มขึ้น 1

• ค่าส่งคืนเมื่อ disjoint เป็น 0 มิฉะนั้นให้คืนค่า -1

ตัวอย่าง(Python)

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

class Solution(object):
   def find(self, x):
      if self.parent[x] == -1:
         return x
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]
   def union(self,x,y):
      parent_x = self.find(x)
      parent_y = self.find(y)
      if parent_x == parent_y:
         return
      self.parent[parent_y] = parent_x
   def minimumCost(self, n, connections):
      self.parent = [ -1 for i in range(n+1)]
      disjoint = n-1
      cost = 0
      c = sorted(connections,key=lambda v:v[2])
      i = 0
      while i<len(c) and disjoint:
         x = c[i][0]
         y = c[i][1]
         if self.find(x)!=self.find(y):
            disjoint-=1
            cost+=c[i][2]
            self.union(x,y)
            i+=1
         return cost if not disjoint else -1
ob = Solution()
print(ob.minimumCost(3, [[1,2,5], [1,3,6], [2,3,1]]))

อินพุต

3
[[1,2,5],[1,3,6],[2,3,1]]

ผลลัพธ์

-1