如何求：最小割？

一直没有弄明白“最小割”的求法。

“最大流”可以通过增广路径求解。
但据说，“最小割”可以通过“最大流”求解，
具体该如何求解“最小割”问题呢？

4 个解决方案

#1

最大流最小割定理保证了最大流和最小割数值上相等，并且最大流可以提供一个最小割。所以一切最大流算法都可以拿来做最小割。
当然直接求最小割的算法也是有的，基本都是基于收缩边的思想。

#2

那么，在得到最大流后，
该如何得到最小割的各边呢？

#3

从源点开始在剩余图上bfs，遍历到的点集合是S，没有遍历到的点集是U，连接S-U的所有边就是最小割

#4

引用 3 楼 fancymouse 的回复:

从源点开始在剩余图上bfs，遍历到的点集合是S，没有遍历到的点集是U，连接S-U的所有边就是最小割

cool！