数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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
337 次查看
