专栏文章
关于SPFA,它被我救死了
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minpm4kv
- 此快照首次捕获于
- 2025/12/02 06:17 3 个月前
- 此快照最后确认于
- 2025/12/02 06:17 3 个月前
~呜呜呜,我的SPFA又si了~
在spfa优化到AC中,
坏消息:Dep优化属于补救性优化,轻轻一卡就卡掉了,只需要让源点与每个节点连一条边权特别大的边,优化就会失效,就会退化为DFS-spfa(假算法)或普通SPFA加logn常数(如果Dep相同就按广搜序的话...)
好消息:经数学证明,从理论时间复杂度的角度来说,拓扑排序优化属于绝对正优化,并且可以和其他优化配合用!(假如我又弄出一个优化)
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...