BZOJ 1797 [Ahoi2009]Mincut 最小割


题目链接: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...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1797 [Ahoi2009]Mincut 最小割


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , ,