使用 Python 連線城市並最小化成本

假設有 N 個城市，編號從 1 到 N。我們有一些連線，其中每個連線 [i] 是 [城市1，城市2，成本]，這表示將城市1 和城市2 連線在一起的成本。我們必須找到最小成本，以便對於每一對城市，都存在一條連線路徑（可能長度為 1）將這兩個城市連線在一起。成本是所用連線成本的總和。如果任務不可能完成，則返回 -1。

所以如果影像是這樣的 -

那麼輸出將是 6，選擇任意兩個城市將連線所有城市，因此我們選擇最小的 2，[1, 5]

為了解決這個問題，我們將遵循以下步驟 -

  • 定義一個名為 find() 的方法，它將接收 x

  • 如果 parent[x] 為 -1，則返回 x

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

  • 返回 parent[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，cost := 0

  • c := conn 的排序列表，根據成本對其進行排序

  • i := 0

  • 當 i < c 的長度且 disjoint 不為 0 時

    • x := c[i, 0] 且 y := c[i, 1]

    • 如果 find(x) 與 find(y) 不相同，則將 disjoint 減 1，將 cost 增加 c[i, 2]，並執行 union(x, y)

    • 將 i 增加 1

  • 當 disjoint 為 0 時返回 cost，否則返回 -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

更新於: 2020年4月30日

337 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告