如果我们求出了最大流 f ,那么残余网络中一定不存在 s 到 t 的增广路经,也就是 S 的出边一定是满流, S 的入边一定是零流,于是有:
结合前面的不等式,我们可以知道此时 f 已经达到最大.
通过 最大流最小割定理,我们可以直接得到如下代码:
这个割边数量并没有保证是在最小割的前提下,所以最下方的例题不能做如此简单的处理.具体解法可以参见题解,不要被这句话误导了.
问题模型¶
这是一个经典的 二者选其一 的最小割题目.我们对于每个集合设置源点 s 和汇点 t ,第 i 个点由 s 连一条容量为 a_i 的边,向 t 连一条容量为 b_i 的边.对于限制条件 uvw ,我们在 uv 之间连容量为 w 的双向边.
注意到当源点和汇点不相连时,代表这些点都选择了其中一个集合.如果将连向 s 或 t 的边割开,表示不放在 A 或 B 集合,如果把物品之间的边割开,表示这两个物品不放在同一个集合.