众所周知,Dinic 删去一条边后,重新跑最大流的复杂度可能无法接受,此时需要进行退流操作。即,如果割掉 u→v 的边,我们会:
- 从 u 到源点跑最大流。
- 从汇点到 v 跑最大流。
- 将 u→v 正边、反边的剩余流量都设为 0。
但是我举出了一组不知道对不对的反例。考虑下面的图:

每条边的流量都是 1。设从左往右四个点的编号依次是 1,2,3,4,在跑完最大流后,路径 1→3→4,1→2→4 被增广,一些反向边的剩余流量增加了 1,下图画出了跑完最大流后,所有有剩余流量的边:

如果要删去边 2→3,我们会跑 2 到 1,以及 4 到 3 的最大流。但是我模拟一遍过后,发现所有的流量全都被退掉了,图变成了最开始的样子。

经过多次检查,我没有发现前述过程中中的漏洞,求大佬解答 qwq