python实现 CCF201812-4 数据中心
试题编号: | 201812-4 |
试题名称: | 数据中心 |
时间限制: | 1.0s |
内存限制: | 512.0MB |
问题描述: |
样例输入 4 样例输出 4 样例说明 下图是样例说明。 |
一、解题思路分析
1.通过kruskal算法求最小生成树最大的边
二、满分代码
def find(forest, item):
"""返回未变化的双亲节点,如果变化了找到未变化的为止"""
if forest[item] != item: # 双亲节点和当前节点不一致,变化了说明这条边已经添加MST
forest[item] = find(forest, forest[item]) # 找到双亲节点未变化的点
return forest[item]
def Kruskal(nodes, edges):
'''基于不相交集实现Kruskal算法'''
forest = {}
MST = []
for item in nodes: # 双亲节点初始化
forest[item] = item
edges = sorted(edges, key=lambda element: element[2]) # 排序
num_sides = len(nodes) - 1 # 最小生成树的边数等于顶点数减一
for e in edges:
node1, node2, _ = e
parent1 = find(forest, node1) # 找到node1的双亲节点
parent2 = find(forest, node2)
if parent1 != parent2: # 双亲节点不一致
MST.append(e)
num_sides -= 1
if num_sides == 0: # 注意控制条件是最小生成树的边满足条件
return MST
else: # 改变该顶点的双亲节点
forest[parent1] = parent2
def main():
n = int(input())
m = int(input())
root = int(input())
nodes = list(range(1, n+1))
edges = []
for i in range(m):
temp = list(map(int, input().split()))
edges.append(temp)
mst = Kruskal(nodes, edges)
tmax = 0
for ms in mst:
if ms[-1] > tmax:
tmax = ms[-1]
print(tmax)
main()