样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明

思路：

链接：https://pan.baidu.com/s/17JQtM3O6LpHHZ5diUTXS5w
提取码：0naq

这道题其实就是求最小生成树的最大权值。求最小生成树有两种算法，Prim算法和Kruskal算法。关于这两个算法的ppt讲解见上方百度网盘链接。以下代码使用的是并查集的方法去解决。并查集算法教学视频

代码

from operator import attrgetter
class Edge(object):
    def __init__(self,From,to,distance):
        self.From = From
        self.to = to
        self.distance = distance
father = []
result = 0
def init(number):   #初始化father列表
    global father
    father = [-1] * number   #-1代表当前元素没有父节点

def find_root(x):   #找到元素x的父节点
    global father
    x_root = x
    while father[x_root] != -1:
        x_root = father[x_root]
    return x_root

def union(x,y,distance,rank):   #合并
    global father
    global result
    x_root = find_root(x)
    y_root = find_root(y)
    #两个元素的父节点不同，说明不在一个集合里，也即不会构成回路
    if x_root != y_root:
    #使用按秩合并的方法进行优化
        if rank[x_root] > rank[y_root]:
            father[y_root] = x_root
        elif rank[x_root] < rank[y_root]:
            father[x_root] = y_root
        else:
            father[x_root] = y_root
            rank[y_root] += 1
        result = distance


vNum = int(input())
sNum = int(input())
root = int(input())

init(vNum + 1)  #加1的原因是，列表下标是从0开始，而结点从1开始
lists = []
for i in range(sNum):
    From,to,distance = map(int,input().split())
    edge = Edge(From,to,distance)
    lists.append(edge)
lists = sorted(lists,key = attrgetter('distance'))  #按距离的大小，从小到大排序
rank = [0] * (vNum + 1)
for i in range(sNum):
    edge = lists[i]
    From,to,distance = edge.From,edge.to,edge.distance
    union(From,to,distance,rank)
print(result)