BZOJ 1797 [Ahoi2009]Mincut 最小割

发布于 2017-05-27  220 次阅读


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

题意:一个有向图,求对于每一条边,是否可以出现在最小割中,是否一定出现在最小割中....


BZOJ3258 调教了一个早上.... 狂 WA 狂 TLE,实在写不下去了... 发现了这道题也能学习最小割唯一性判定相关姿势... 于是很快就过了....

首先对做完最小割的残量网络 tarjan 缩点....

结论是这样的:

  • 一条边为最小割的可行边,当且仅当两端点不在同一强连通分量中 (1
  • 一条边为最小割的必须边,当且仅当两端点分别与 S,T 在同一强连通分量中 (2

对于 (1 的证明:将原图缩点后剩下的边就都是满流的边了,这样新图中的任意一组割都对应一组原图的最小割,随意选择一组能割开两端点所在 scc 的即可证明

对于 (2 的证明:首先 (2 一定满足 (1,我们尝试增大该边容量,那么一定有了一条新的 S->u->v->T 的通路,最大流可以增大继续跑,所以 u->v 为必须边

另外有一个 bzoj3258 的 WA 点提示... 第一步求最短路要 long long...

 


一个非常弱的准退役OIER