传送门
来自题解：luogu/wiki/show?name=题解+P3385
1.BellmanFord
通过BelmanFord求出最短路，然后在进行一遍松弛操作，如果可以再松弛说明存在负环，否则不存在。
2.SPFA
SPFA有两种实现方法。一个是BFS一个是DFS。
1.BFS
BFS版的判断标准：是否存在某个节点入队超过n次
BFS_SPFA的期望时间复杂度是O(ke)，其中k为所有顶点进队的平均次数。
如果存在负环嘛，这个期望的时间复杂度就真的是期望了。
2.DFS
DFS版判断标准：否存在一点在一条路径上出现多次来判断。
时间复杂度如果没记错是O(nlogn)的。
3.DFS优化
既然我们只需要判断负环，那么就相当于我们需要找到一条权值和为负的回路。
既然我们只需要找到权值和为负的回路，那不妨使距离数组d初始化为0。
这样处理后，第一次拓展只会拓展到与起点相连边权为负的边。
那么我们就分别枚举所有的点作为起点，如果已经找到一个负环就不再继续枚举。
根据SPFA，我们找到的负环一定包含当前枚举的这个点。（因为这个点出现了两次啊）
——代码
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 6 const int MAXN = 001; 7 int T, n, m, cnt; 8 int head[MAXN], to[MAXN], next[MAXN], val[MAXN], dis[MAXN]; 9 bool vis[MAXN], flag; 10 11 inline void add(int x, int y, int z) 12 18 19 inline void spfa(int u) 20 34 else spfa(v); 35 } 36 } 37 vis[u] = 0; 38 } 39 40 int main() 41 57 for(i = 1; i <= n && !flag; i++) spfa(i); 58 if(flag) printf("YE5\n"); 59 else printf("N0\n"); 60 } 61 return 0; 62 }View Code
上一篇：[HDU2896]病毒侵袭（AC自动机）
下一篇：[luoguP1364] 医院设置（树的重心）
模板 spfa 负环 最短路 Bellman-Ford
