保存帖子
发现
索引
热门
陶片放逐
关于
关于SPFA和差分约束的一些疑问
板块
学术版
楼主
questRush
当前回复
12
已保存回复
12
发布时间
2020/7/23 11:50
上次更新
2023/11/6 22:31:32
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于SPFA和差分约束的一些疑问
questRush
楼主
2020/7/23 11:50
s
p
f
a
spfa
s
p
f
a
假的复杂度是不是专指
d
f
s
dfs
df
s
版的
s
p
f
a
spfa
s
p
f
a
能被精心构造的数据卡成指数级?
所谓的指数级是不是指
O
(
2
∣
V
∣
O(2^{|V|}
O
(
2
∣
V
∣
)?
如果使用 spfa 但不使用任何优化,是不是保证复杂度最差和 Bellman-Ford 一样达到
O
(
∣
V
∣
∣
E
∣
)
O(|V||E|)
O
(
∣
V
∣∣
E
∣
)
?
在差分约束题目中,比如 P3275 糖果,如果粗略计算 mn 的范围超过时限,是不是基本可以否定正解是用 spfa?
2020/7/23 11:50
加载中...