使用 Python 以最低成本连接 city\

pythonserver side programmingprogramming更新于 2025/11/12 23:08:17

假设有 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])
返回 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
while 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]]))