P4180 [BJWC2010] 严格次小生成树

发布时间 2023-11-23 09:38:50作者: 御坂夏铃

如果有两条在最小生成树上的边被换掉了,那么原树会被分成三个连通块。

考虑新加的两条边,保留权值较小的那一条,这样还剩两个连通块。而删除的两条边至少有一条能连通这两个连通块,所以可以保留那条边。

并且新加的两条边中权值较大的那一条肯定大于等于我们保留的边,否则与最小生成树的前提不符。

这样就证明了删除两条边的任意一种方案都存在一种不劣的删除一条边的方案。对于删除更多边的情况,直接归纳即可。

所以仅仅需要考虑删除一条边的情况。倍增时记录最大值和严格次大值,最后枚举不在最小生成树上的边尝试替换。

把更新的过程写成一个函数会让代码简洁很多。