负环就不应该用dfs写
by _ztyqwq @ 2018-07-16 20:24:50
@[刷题永动机](/space/show?uid=73645)
你有听说过一本叫做一本通.提高篇的毁青春的书吗，那上面说判负环DFS跑的很快，然后我信了他的鬼话。
by jacktang @ 2018-07-17 09:39:50
@[jacktang](/space/show?uid=53898) 妙啊
by smzzl @ 2018-07-20 22:43:07
@[jacktang](/space/show?uid=53898) %%% 真的妙
by ganaATpiedra_org @ 2018-07-21 11:39:24
dfs25分+1
by Stella_Yan @ 2018-07-22 21:06:41
@[jacktang](/space/show?uid=53898) 我也是DFS然后直接TLE*15
by CreeperLordVader @ 2018-07-25 14:45:54
>如果题目保证数据随机那就用dfs比bfs快，否则就用bfs。bfs复杂度上界是 O(nm)O(nm) ，而dfs复杂度是指数级的。
by n0000000000o @ 2018-07-25 16:46:46
~~不是我说的~~
by n0000000000o @ 2018-07-25 16:47:09
@[jacktang](/space/show?uid=53898) 似乎是上面说的是判断**正环**。。。
by Juanzhang @ 2018-07-31 13:26:30
@[小光](/space/show?uid=73934) 嗯，是的，那本书说负环同理，以正环为例。（P140,"1.使用SPFA快速查找负（正）环"的下一行。"由于正负环本质一样，所以下文由于例题需要只讨论正环的情况。"）
（然而事实上正负环也的确一样的吧。。。。无非是跑最长路和跑最短路的区别。。），另外那本书上其实对SPFA讲了很多优化，不是我在黑那本书啊。。。我只是想吐槽一下。。
by jacktang @ 2018-07-31 19:31:44