Back to Leetcode

Readme

Union_Find/3600.Maximize-Spanning-Tree-Stability-with-Upgrades/Readme.md

latest1.2 KB
Original Source

3600.Maximize-Spanning-Tree-Stability-with-Upgrades

突破口是二分搜值。如果猜测全局最小的stability是T的话,尝试能否用最小生成树的方法构造出一棵树来。

当固定全局最小的stability是T之后,那么哪些edge能用哪些不能用就一目了然了。对于must的那些边,如果存在stability小于T的,那么显然无解。对于非must的边,如果2*stability<T,那么必然排除作为构造树的候选;反之就可以作为候选,同时我们需要根据2s和T的比较,标注这条边“是否需要upgrade”。

有了所有的候选边,我们就可以用Kruskal算法构造“最小生成树”。只不过这里优化的不是总边的权重,而是“upgrade的次数”。我们将所有边按照“是否需要upgrade”排序即可(其实就是0或者1),优先选用不需要upgrade的边实现更多的union。如果发现一个候选边的两个端点已经union在一起了,那么这条边其实就可以放心地舍弃而没有任何副作用。注意处理完所有的边之后还需要判断两点:是否恰好用到了n-1条边(否则说明可能有环),是否所有的点的find都相同(否则说明可能有不联通的区域)。