关于SPFA和差分约束的一些疑问
  • 板块学术版
  • 楼主questRush
  • 当前回复12
  • 已保存回复12
  • 发布时间2020/7/23 11:50
  • 上次更新2023/11/6 22:31:32
查看原帖
关于SPFA和差分约束的一些疑问
278521
questRush楼主2020/7/23 11:50
  • spfaspfa 假的复杂度是不是专指 dfsdfs 版的 spfaspfa 能被精心构造的数据卡成指数级？
  • 所谓的指数级是不是指 O(2∣V∣O(2^{|V|})?
  • 如果使用 spfa 但不使用任何优化，是不是保证复杂度最差和 Bellman-Ford 一样达到 O(∣V∣∣E∣)O(|V||E|)？
  • 在差分约束题目中，比如 P3275 糖果，如果粗略计算 mn 的范围超过时限，是不是基本可以否定正解是用 spfa？
2020/7/23 11:50