关于 dinic求最大流/费用流 优化后的时间复杂度的一些疑问
  • 板块学术版
  • 楼主tobie
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/5 22:07
  • 上次更新2023/10/27 21:47:23
查看原帖
关于 dinic求最大流/费用流 优化后的时间复杂度的一些疑问
192044
tobie楼主2022/7/5 22:07

RT。

我现在正在使用的模板都仅使用了当前弧优化,而没有使用多路增广优化。

模板题中,,Dinic如果少了当前弧会跑得很慢(尤其是#9测试点,不加当前弧一定T),而加了当前弧会很快

但是多路增广对评测结果似乎没有什么影响。

所以,目前根据我的经验来说,当前弧优化在网络流中是必要的,而多路增广有没有都没有关系。其它洛谷题目也没有特别卡某种优化的情况。

求各路大佬解答一下:

  1. 多路增广对时间复杂度的影响有多大
  2. 为什么不加当前弧时间复杂度会增大

bdfs无果,望解答

2022/7/5 22:07
加载中...