众所周知,求最大流要是没有反向边,基本都是错的
那为什么反向边能修正错误的增广
查了一些资料,好像没有什么严格证明的样子,可能图论还是太复杂了点
不过还是找到了 PKU camp 的 PPT,感觉说的还不错,大概意思就是反向边可用于二路合并
(你刚才说我画的丑是吧)
考虑某种情况,如图有一条增广路通过 \(a \to b\) 的路径,\(flow = n\)
那么至少说明,
边 \(e1,e4\) 有 \(cap-flow=n\),
如果此时已经跑不动了,那就只能增广到这里得到最大流 \(n\)
假如添加了反向边的机制,发现能 \(b \to a\) 反向流动 \(flow=n-k\) 的流量
至少说明,
边 \(e2,e3\) 有 \(cap-flow=n-k\)
此时的情况和图的上半部分对应
添加了反向边后的情况其实等价于下半部分,把 \(n-(n-k)\) 的流退回去后
我们可以得到最大流 \(maxflow=2n+k\)
关键是,这是在不影响其他边的前提下获得的增广(\(e1,e2,e3,e4\) 均不受影响)
因此我们可以感性地认为反向边的策略是正确的