萌 新 求助 退 流
  • 板块学术版
  • 楼主ducati寄
  • 当前回复15
  • 已保存回复15
  • 发布时间2023/6/7 15:43
  • 上次更新2023/10/23 13:45:09
查看原帖
萌 新 求助 退 流
87064
ducati寄楼主2023/6/7 15:43

众所周知,Dinic 删去一条边后,重新跑最大流的复杂度可能无法接受,此时需要进行退流操作。即,如果割掉 u→vu \to v 的边,我们会:

  • 从 uu 到源点跑最大流。
  • 从汇点到 vv 跑最大流。
  • 将 u→vu \to v 正边、反边的剩余流量都设为 00。

但是我举出了一组不知道对不对的反例。考虑下面的图:

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

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

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

2023/6/7 15:43
加载中...