社区讨论

萌 新 求助 退 流

学术版参与者 6已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@lo2h4bs1
此快照首次捕获于
2023/10/23 13:45
2 年前
此快照最后确认于
2023/10/23 13:45
2 年前
查看原帖
众所周知,Dinic 删去一条边后,重新跑最大流的复杂度可能无法接受,此时需要进行退流操作。即,如果割掉 uvu \to v 的边,我们会:
  • uu 到源点跑最大流。
  • 从汇点到 vv 跑最大流。
  • uvu \to v 正边、反边的剩余流量都设为 00
但是我举出了一组不知道对不对的反例。考虑下面的图:
每条边的流量都是 11。设从左往右四个点的编号依次是 1,2,3,41,2,3,4,在跑完最大流后,路径 134,1241 \to 3 \to 4,1 \to 2 \to 4 被增广,一些反向边的剩余流量增加了 11,下图画出了跑完最大流后,所有有剩余流量的边:
如果要删去边 232 \to 3,我们会跑 2211,以及 4433 的最大流。但是我模拟一遍过后,发现所有的流量全都被退掉了,图变成了最开始的样子。
经过多次检查,我没有发现前述过程中中的漏洞,求大佬解答 qwq

回复

15 条回复,欢迎继续交流。

正在加载回复...