LuoguP1525(并查集)

题目大意

给定$n$个点$m$条边,每条边有权值,要求分成两个点集,使两个点集的各自边权最大值最小。

分析

这道题我一开始也没有想到什么做法,后来看来题解后才想到。首先我们可以发现贪心的选择才是最优的,只有权值最大的那条边的两个点不在同一个点集中答案才会最优,同理对于权值次大的边…

所以,我们首先可以进行一次排序。

接下来考虑,对于当前没有决定的权值最大的边的两个点,我们肯定要使它们不在一个点集中,如果已经在一个点集中了,那么就直接输出当前边的权值。

那如果不在一个点集中,我们就要尽量让这两个点与对另外一个点来说比边权最大的那个点在一个点集中,因为已经排过序了,所以就是之前第一个访问该点的另外一个点在一个点集中。

可能有点复杂,可以看代码思考一下。

代码

为了保证网站的安全,特将代码从solution中将code分离。
Code : 戳我!!!!!(速度较慢,请耐心等待)