P4126 [AHOI2009]最小割

https://www.cnblogs.com/dugudashen/p/6228304.html
求解一张有向图中关于最小割的可行边和必须边，可行边定义为存在一种最小割包含这条边，必须边定义为任意一种最小割包含这条边。

可行边的条件：

满流

对于边<u,v>不存在从u到v的增广路

首先如果不满流，那么一定存在一条满流的权值更小的边。
如果存在增广路那么一定不可能是割边，因为它并没有割开点集。

必须边的条件：

满流

并且缩点之后<u,v>这条边直接连接了S和T所在的连通块

在缩点之后，如果S能够到u，v能够到T，那么一定存在最小割的可行边可以替代这个边，所以就不是必须边了。

最小割必须边的另一种理解是扩大容量后能够增大最大流的边。那么由于原图已经不存在增广路，所以扩大容量后能够增大最大流的边只会是连接S和T所在联通分量的边。

总结

以上是生活随笔为你收集整理的P4126 [AHOI2009]最小割(网络流/最小割）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。