[学习笔记] 一点SPFA的随笔

oi

一点SPFA的随笔

大佬勿喷orz…都是些很基础的东西,因为我太菜了

  1. SPFA有一个$O(m\log{n})$的堆优化策略(见魔法猪学院),而且代码很短,应该卡的没那么严重。
  2. SPFA(bfs)可以解决很大一部分状压DP的问题(见软件补丁问题、愤怒的小鸟(需要Ofast优化过)),虽然速度会慢很多,作为下策吧..应该可以骗一半以上的分。
  3. SPFA支持动态加点(详见Poq的魔法森林解法),如果能够可持久化d数组会很爽。
  4. SPFA的queue支持定制,queue中装的是转移,可以当成dp来思考(详见FULL TANK?)(可以解决k短路,k步最短路等等问题(虽然效率不行))(详见魔法猪学院配合A*,还有一个k步最短路的用矩阵快速幂解的?)