python实现 CCF201812-4 数据中心

一、解题思路分析

1.通过kruskal算法求最小生成树最大的边

二、满分代码

def find(forest, item):"""返回未变化的双亲节点，如果变化了找到未变化的为止"""if forest[item] != item: # 双亲节点和当前节点不一致，变化了说明这条边已经添加MSTforest[item] = find(forest, forest[item])  # 找到双亲节点未变化的点return forest[item]def Kruskal(nodes, edges):'''基于不相交集实现Kruskal算法'''forest = {}MST = []for item in nodes:  # 双亲节点初始化forest[item] = itemedges = sorted(edges, key=lambda element: element[2])  # 排序num_sides = len(nodes) - 1  # 最小生成树的边数等于顶点数减一for e in edges:node1, node2, _ = eparent1 = find(forest, node1) # 找到node1的双亲节点parent2 = find(forest, node2)if parent1 != parent2:     # 双亲节点不一致MST.append(e)num_sides -= 1if num_sides == 0:     # 注意控制条件是最小生成树的边满足条件return MSTelse:                  # 改变该顶点的双亲节点forest[parent1] = parent2def 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 = 0for ms in mst:if ms[-1] > tmax:tmax = ms[-1]print(tmax)main()