原始对偶算法复杂度里的 f 是什么东西啊
  • 板块学术版
  • 楼主滑蒻稽
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/3/3 10:59
  • 上次更新2023/10/28 07:24:20
查看原帖
原始对偶算法复杂度里的 f 是什么东西啊
113181
滑蒻稽楼主2022/3/3 10:59

用 STL 的优先队列的话 Primal-Dual 算法的时间复杂度是 O(nm+fmlogm)O(nm+fm\log m),这里面的 f 说是最大流?

但费用流模板里最大流 2311\le 2^{31}-1,理论上套上复杂度直接爆炸,但是事实上可以通过。

这个 f 到底是什么东西或者说怎么算啊

2022/3/3 10:59
加载中...