负环

传送门

来自题解：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

上一篇：[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）

下一篇：[luoguP1169] [ZJOI2007]棋盘制作（单调栈）

---

spfa 最短路 模板 负环 Bellman-Ford