关于spfa
知识点
原始版 ---裸
应用：
一、判负环
两种方法
1.跑单源点，如果某一个点入队了n-1次，存在
2.对于每个点spfa，如果此源点反被其他点更新，存在
证明：点i作为源点，d[i]==0 若i被更新，d[i]<0 定存在负环
二、网络流最小费用最大流
无限spfa直到没有可流的量
在原始spfa中，加入流量限制 ，记录入边
每次spfa结束后沿入边更新流量即可
三、差分约束
建图更复杂，建好图就很水了
优化：
SLF
双向队列优化 若d[v]<d[head] 插入队首 否则队尾
堆优化：手写小顶堆或者STL优先队列
优点
跑稀疏图较快且可以跑负边权
复杂度 O(E*K) K为常数且大致为1~2
题目分析：
Spfa其实很简单啊，只是建模比较麻烦了
1.首先今上午的考试题，spfa中加一个dp，存到现在点用了几个血包，但由于恶心的出题人卡了你一下，你需要一个SLF优化或者转成dijkstra
知识点：dp+优化
2.某个题目吧，大致是一个n*m的方格图，只能沿着边走，问从一个坐标到另一个坐标最少需要转几次弯。 拆点，每个格点拆为上下左右四个点，表示向哪个方向走，想到拆点之后建边就很简单了
知识点：拆点
3.一道很裸的判负环的题，方法上面又讲，代码也很简单
知识点：判负环
4.分层spfa，有一些层次，每个层次只能向下一层次建边
知识点：建模
大概见过的题目好像就只有这些了。。。
考得多的其实是拆点和建边吧
（完）
原文：http://www.cnblogs.com/wsy01/p/7506417.html