或许只是因为数据随机而 spfa 常数小点,但是还不会 dij 的加势 /kk
我自己的 spfa+SLF+dinic -O2 945ms
by Ryo_Yamada @ 2022-01-05 21:27:03
不卡spfa的图spfa该比dij快吧 /qd
by Krystallos @ 2022-01-05 21:28:02
毕竟本身 SPFA 在随机数据下的期望复杂度就比 dij 优 /fad
by Legitimity @ 2022-01-05 21:32:14
@[Krystallos](/user/124683) 但是我 dij 不吸氧会 T 掉/kk
by vectorwyx @ 2022-01-05 21:36:43
感觉就算 dij 常数比 spfa 大也不至于不开 O2 连 1s 都卡不进去?
by vectorwyx @ 2022-01-05 21:37:16
算上priority_queue的常数和本身复杂度$O(nm\log m)$恐怕真的呛 /kk
by Krystallos @ 2022-01-05 21:40:35
我写的dij+dinic也过不了
by Neph @ 2022-01-05 21:57:15
此贴完结,我的 spfa 和 dij 都写错了/hanx。
dij 写成了 堆 优 化 s p f a
by vectorwyx @ 2022-01-05 22:27:03
@[vectorwyx](/user/238408) 看看 panda 的题解,不开 O2 就是过不了的。
by rxjdasiwzl @ 2022-01-05 22:36:09