最大流
反向边
关于此物， 可以从理性和感性两个方面去理解。
理性的话，
根据网络流的一些定义， 流函数即流量\(f(x, y) = -f(y, x)\), 并且对于任意不属于网络中的边\((x, y)\)(包括反向边), \(c(x, y) = 0\) 即反向边容量为0。
增广路的定义为一条从 S 到 T 的路径，满足各边的剩余容量即\(c(x, y) - f(x, y) > 0\)。
当网络中再也找不出增广路时， 就求得了最大流。
当有一股流从\(u\)流过\(v\)， 其实相当于有负流从\(u\)流过\(v\)， 这可以根据斜对称性质脑补一下。
当首先一股流量流经正向边\((u, v)\)时，若\(f(u, v) = x\), 则\(f(v, u) = -x\)。
此时(v, u)的剩余容量\(c'\)为\(x\)。
考虑这个\(c'\)的含义。
网络流的流是一个特殊的东西，反向流量是可以相互抵消的。
当流量流经反向边时， 相当于减少正向边流过来的流量。 这像一个高级的回溯技巧， 而且这是实打实的水啊， 氵朔。
所以流反向边就能实现回溯操作。
感性的话，
流经反向边时， 就可以从正向边上抽取一部分流量，去进行增广。 而为了保证不会使答案变差， 抽取的流量会被反向边前的路径流量所补充。
个人理解是有点暴力地进行增广， 不择手段， 抽就硬抽。(滑稽)
或者把问题具体一点分析， 假设当前路径经过了一条反向边\((u, v)\)， \(S->...->u->v->...->T\)这样的一条路径。
通过手动模拟， 发现流向u点的流量是不会在增广时改变的。 这是为什么呢？
因为之前扩展的一条路径\(S->...->v->u->...->T\)废弃了\(S->...->u\)这条路径上的剩余容量。
要使答案更优， 当然是要充分利用剩余容量， 于是在找到增广路即确定了\(v->u\)退流的可行性后， 就在保证答案不会变差的前提下解放一部分\(v->u\)的流量， 去增广。
Dinic
相较于\(O(nm^2)\)的 EK 算法， Dinic的时间复杂度为\(O(n^2m)\)
嗯？ 好像……感觉……差不多？(小声)
实际上不然。
想一下， 一个\(n\)个点的图要保证联通时边数最小是\(n - 1\)， 即此时是一棵树。
而对于一个网络中， 边数当然不止。 而且还有同样数量的反向边。
所以 Dinic 还是比EK要优秀的。
开始吧！
1-在上面的关于反向边的理解中， 发现每次增广时尽量找短一点的增广路可以避免一些错误。
2-而且， EK一次 BFS 只能找一条增广路， 效率不高。
3-类比与归并排序一次找出多个逆序对从而提升效率， 我们能不能一次找出多条增广路？
所以就决定是你了！ 去吧！ Dinic!
Dinic关于1.的解决方案是每一次跑一遍 BFS 对残量网络建立分层图。
每一次增广我们强制路径上点的层数递增， 从而减少错误以及提升效率。
关于2.3.的解决方案是通过 DFS 每一次榨干一条当前分层图的增广路。 (回溯递归的优势)
这样在一次 BFS 下不停调用 DFS 就能找出当前分层图的所有增广路啦！
他还有两个非常强的优化：
当前弧优化
每一次 BFS 并经过若干次 DFS 后， 在当前的分层图上我们一定再也找不出增广路了。
我们可以记录每一个点扩展时榨干到了第几条边， 下一次增广直接从这条边开始。
这是一个很强的剪枝， 效果拔群， 值得你的 Dinic 拥有！
整体流量优化(应评论区某大佬要求)
我们发现现在的 Dinic 不过在一次 BFS 中多次 DFS, 每次 DFS 也不过找出一条增广路而已。
于是， 这个优化， 应天地生灵的呼唤， 出世了……
不废话了。
假设当前 DFS 到了点\(u\), 当前路径的最小容量为\(min\)。
对于从\(u\) DFS 到了一条增广路后， 我们并不立即返回。
而是继续 DFS \(u\)的其他边， 直到当前\(u\)所累计的流量\(f\)满足\(min = f\)才返回。
这样可以在一次 DFS 中就能多路增广， 简直强无敌！