或者这个东西本身就是错的，求 $hack$
by sunzz3183 @ 2024-04-26 21:00:30
@[sunzz3183](/user/171868) 江东小儿szz666
by zhongpeilin @ 2024-04-26 21:36:42
@[sunzz3183](/user/171868) 江东小儿szz666
by Goliard @ 2024-04-26 21:38:35
@[sunzz3183](/user/171868)
首先明确一下算法流程，没搞错的话，应该是指先（连 $T \to S$ 的边后）求无源汇上下界可行流，然后再把新加的超级源汇删掉，对残量网络求最大流。然后 $f(i)$ 指的是求可行流后的 $i$ 号边的流量。
以下讨论在明确上述流程的基础下进行。如果对流程的理解有误，请指出。
按我理解，$f(i)$ 是可能变小的。毕竟这就是所谓反向边退流嘛。所以按照你的**文字写法**我认为是错误的。又但是，如果你的代码实现和你的文字对不上的话，可能代码实现其实是对的。其实就是，反边的剩余容量也要对应修改为 $f(i)$，以允许将至多 $f(i)$ 的流量退回。
（但是在广泛的实现中，不需要修改流网络，因为直接在残量网络上跑就是对的，或者说，与我前一段的说法是等价的）
by 小粉兔 @ 2024-04-26 23:56:17
上面是感性理解，并不严谨，但是我觉得够用。你可以看一下他人的代码实现以确定算法细节。有疑问 at 我。
by 小粉兔 @ 2024-04-26 23:57:16
@[小粉兔](/user/10703) 嗯，理解了，我也感觉直接减不对，实际实现上也确实不用这么麻烦。但是我测试了 luogu 和 zoj 的数据，好像都能满足跑最大流过程中流量不会小于原来 $f(i)$ 的情况，可以给组 hack 吗？或者结论是正确的，可以给一下证明吗？
by sunzz3183 @ 2024-04-27 09:47:24
@[小粉兔](/user/10703) hack跑出来了qwq，问题已解决，谢谢
by sunzz3183 @ 2024-04-27 14:52:05
sb
by PeyNiKge @ 2024-05-03 15:39:25