BZOJ 2561 最小生成树


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

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


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

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

 


一个蒟蒻oier的博客 |稍有常识的人都能看出,公告里已经说啦注册功能尚未恢复,不要再试啦~想要账号可以在任意一篇文章下评论留下联系方式或者私聊博主qq获取!~