BZOJ 2561 最小生成树

发布于 2017-08-12  135 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2561

题意:一个带权图,加一条边。问至少删几条边使得这条边既可以出现在最小生成树上,也可以出现在最大生成树上。


u->v 可以出现在最小生成树上当且仅当只用边权小于 L 的边无法连通 u->v

于是建图跑最小割,最大生成树同理

 


一个非常弱的准退役OIER