关于费用流时间复杂度
  • 板块学术版
  • 楼主Comentropy泠云
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/1/11 10:55
  • 上次更新2024/1/11 18:05:27
查看原帖
关于费用流时间复杂度
264360
Comentropy泠云楼主2024/1/11 10:55

本人在费用流学习过程中出现了如下疑问:

  1. 据 oi-wiki 指出,SSP 算法不存在一个严格的多项式时间。但是基于 EK 算法的时间复杂度证明,导致这种情况出现的原因是否是负权边?

  2. 在实际实现过程中 dinic 实现和 EK 实现有多大时间差异? EK 会不会被卡?dinic 会不会?

2024/1/11 10:55
加载中...