输入:N = 3,connections = [[1,2,5],[1,3,6],[2,3,1]] 输出:6
时间: 2023-07-02 14:10:41 浏览: 83
连接件计算
这道题目其实就是要求给定一张无向图,找出其中的最小生成树(MST),并计算MST的边权和。
可以使用Kruskal算法或Prim算法来求解。
以下是基于Kruskal算法的Python代码实现:
```python
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
return True
class Solution:
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
connections.sort(key=lambda x: x[2])
uf = UnionFind(N)
num_edges = 0
total_cost = 0
for u, v, w in connections:
if uf.union(u-1, v-1):
num_edges += 1
total_cost += w
if num_edges == N - 1:
break
return total_cost if num_edges == N - 1 else -1
```
其中,UnionFind类是并查集数据结构,用于判断是否形成环路。
Kruskal算法的基本思想是按边权从小到大顺序遍历所有边,每次选择一条边,如果这条边的两个端点不在同一个连通块中,则将这条边加入MST中,并合并两个连通块。最终得到的MST即为所求。
阅读全文