社区讨论
萌 新 求助 退 流
学术版参与者 6已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @lo2h4bs1
- 此快照首次捕获于
- 2023/10/23 13:45 2 年前
- 此快照最后确认于
- 2023/10/23 13:45 2 年前
众所周知,Dinic 删去一条边后,重新跑最大流的复杂度可能无法接受,此时需要进行退流操作。即,如果割掉 的边,我们会:
- 从 到源点跑最大流。
- 从汇点到 跑最大流。
- 将 正边、反边的剩余流量都设为 。
但是我举出了一组不知道对不对的反例。考虑下面的图:

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

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

经过多次检查,我没有发现前述过程中中的漏洞,求大佬解答 qwq
回复
共 15 条回复,欢迎继续交流。
正在加载回复...