口胡。
考虑先点双找出来,对每条割边先按权升序排,再判断是否删了这条边后,s 到 t 就不在联通。跟我一样不怎么会维护的可以写个 LCT 就可以。
找割边,找所有可行路径方案,判 -1 的情况,接下来找到一条可行方案,找到上面权最小的割边,那么可以贡献答案。再者,可以删掉上面任一条边,再反复这个做法,即可找到删 2 条的答案。
2023-09-30 23:16:40
口胡。
考虑先点双找出来,对每条割边先按权升序排,再判断是否删了这条边后,s 到 t 就不在联通。跟我一样不怎么会维护的可以写个 LCT 就可以。
找割边,找所有可行路径方案,判 -1 的情况,接下来找到一条可行方案,找到上面权最小的割边,那么可以贡献答案。再者,可以删掉上面任一条边,再反复这个做法,即可找到删 2 条的答案。