「感性认识」网络流中反向边的正确性

众所周知，求最大流要是没有反向边，基本都是错的

那为什么反向边能修正错误的增广

查了一些资料，好像没有什么严格证明的样子，可能图论还是太复杂了点

不过还是找到了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$均不受影响）

因此我们可以感性地认为反向边的策略是正确的