fAKe
by Karrγ5307 @ 2020-03-23 11:44:03
fAKe
by _Zhumingrui @ 2020-03-23 11:53:14
@[_Zhumingrui](/user/319801) fake的意思是假复杂度么
by ZHAKWF @ 2020-03-23 11:53:48
严格来讲这个复杂度也是 $O(n^4)$ 的，只不过实际表现很~~玄学~~好，据我所知现在只有 bfs 能真正做到 $O(n^3)$。我记得去年 ICPC 就有一道卡 dfs 做法的 KM 题，你可以去做做。
by MKCCT @ 2020-03-23 12:00:44
@[weapon_zipper](/user/88207) 谢谢了 很感谢也就是说 slack也不是标准的O(n^3)么？
by ZHAKWF @ 2020-03-23 12:04:06
@[Zenith_Habitant](/user/103604) 是的，基本上你现在在所有博客上见到的那些自称是 $O(n^3)$ 的 dfs 做法其实都是 $O(n^4)$，真正的 $O(n^3)$ 板子你可以去 UOJ 上找。
by MKCCT @ 2020-03-23 12:06:23
fAKe lz
by _Herobrine_ @ 2020-03-23 12:10:42