@[EternalAlexander](/space/show?uid=48355)
1、O(nm)过1e4有点卡是事实，我去把时限放开一点（
2、一般来说图论建模题很少有会把时间复杂度卡到上限的毒瘤题，比如你见过除了最大流加强版之外有强行卡死dinic/isap的网络流吗……
by chen_zhe @ 2018-12-21 20:08:11
找负环dfs——spfa本来就比bfs——spfa快，你说的那个时间复杂度是求最短路的时间复杂度@[EternalAlexander](/space/show?uid=48355)
by flowerletter @ 2018-12-21 20:08:11
@[EternalAlexander](/space/show?uid=48355) 问题就在于仅仅在找负环的情况下，dfs-spfa就是比bfs-spfa快。
（不过这个卡bfs-spfa的行为确实是毒瘤了）
by StudyingFather @ 2018-12-21 20:08:25
而你看那些写dfs——spfa的人基本每个点都是个位数毫秒，根本不卡常
by flowerletter @ 2018-12-21 20:09:42
@[StudyingFather](/space/show?uid=22030) @[白衣渡川](/space/show?uid=55650) 问题是这玩意复杂度不对啊...面对随机数据dfs-spfa的表现确实非常优秀但是是可以构造数据卡成指数级的...
P3385现在dfs-spfa就过不去
by EternalAlexander @ 2018-12-21 20:10:52
都快9102了怎么还有dfs的..
by ButterflyDew @ 2018-12-21 20:13:24
@[白衣渡川](/space/show?uid=55650) @[StudyingFather](/space/show?uid=22030)
两位是认真的嘛？指数算法比多项式算法快？
xswl
by 一扶苏一 @ 2018-12-21 20:13:59
@[EternalAlexander](/space/show?uid=48355) 按你怎么说干嘛要有spfa，复杂度O(nm),比dij慢，代码比floyd长，对吧
by flowerletter @ 2018-12-21 20:15:27
@[白衣渡川](/space/show?uid=55650) 您的dij能跑负权吗
by EternalAlexander @ 2018-12-21 20:16:07
@[一扶苏一](/space/show?uid=65363) 随机图中远远达不到指数级，而且dfs_spfa真的比bfs_spfa在随机图判负环的时候快
by flowerletter @ 2018-12-21 20:16:41