一道判断负环的模板题。
这里主要介绍三种判断负环的方法。
1.BFS_SPFA方法A
我们可以通过记录每个点的入队次数来判断负环是否存在，不难看出：一个点的入队次数一旦超过n次，则图中一定有负环存在。效率不高，不再提供代码。
2.BFS_SPFA方法B
我们可以记录每个点到源点最短路上经过了几个点，一旦超过n个，则负环一定存在，正确性比较显然、不再赘述。
这个方法为什么会比方法A效率高呢？举个例子:在一个由n个点构成的负环中，方法A要将此环遍历n次，而方法B遍历1次就行了．
３.DFS_SPFA方法
我们只需将SPFA改用DFS实现, 然后应用方法B, 我们就能高效的求出负环了.
愉快的写完代码,提交完成,TLE. mengbi了一会下了组数据后发现，其实大多情况下该算法表现的十分优秀.
DFS_SPFA
经过思考发现：如果一个图没有负环的话，以上方法就像一个弱化版本的SPFA，效率大大降低．所以该方法还是要慎用．
总结：
DFS_SPFA由于它的不稳定性，还是要慎用的．因为我们无法保证图中一定有负环（保证了还判什么）．
BFS_SPFA的方法A就不考虑了, 方法B比他优秀的多....
总体来说个人认为求稳的话,还是使用BFS_SPFA比较保险．
AC代码：
这里给出了BFS方法B和DFS的方法:
#include <cstring> #include <cstdio> #include <cctype> #include <queue> inline void read(int & x) { int k = 1; x = 0; char c = getchar(); while (!isdigit(c)) if (c == '-') c = getchar(), k = -1; else c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); x *= k; } int n, m, cnt, x, y, z, T, u, f[2020], d[2020], v[2020], k[2020], flag; struct Edge { int v, w, nxt; } e[7000]; inline void addedge(int a, int b, int z) { ++cnt, e[cnt].nxt = f[a], e[cnt].v = b, e[cnt].w = z, f[a] = cnt; } inline bool BFS_SPFA(void) { memset(d, 0x3f, sizeof(d)); memset(v, false, sizeof(v)); d[1] = 0, v[1] = 1, k[1] = 0; std::queue<int> Q; Q.push(1); while (!Q.empty()) { u = Q.front(), Q.pop(), v[u] = 0; for (int i = f[u]; i != -1; i = e[i].nxt) if (d[e[i].v] > d[u] + e[i].w) { d[e[i].v] = d[u] + e[i].w, k[e[i].v] = k[u] + 1; if (k[e[i].v] > n) return false; if (!v[e[i].v]) v[e[i].v] = 1, Q.push(e[i].v); } } return true; } void DFS_SPFA(int u) { v[u] = true; for (int i = f[u]; i != -1; i = e[i].nxt) if (d[e[i].v] > d[u] + e[i].w) { d[e[i].v] = d[u] + e[i].w; if (v[e[i].v] == 1) { flag = 1; return; } DFS_SPFA(e[i].v); } v[u] = false; } inline void Work(void) { flag = 0; memset(d, 0x3f, sizeof(d)); memset(v, false, sizeof(v)); d[1] = 0; DFS_SPFA(1); if (flag) puts("YE5"); else puts("N0"); } signed main() { read(T); for (int plk = 1; plk <= T; ++plk) { memset(f, -1, sizeof(f)); cnt = 0; read(n), read(m); for (int i = 1; i <= m; ++i) { read(x), read(y), read(z); addedge(x, y, z); if (z >= 0) addedge(y, x, z); } if (!BFS_SPFA()) puts("YE5"); else puts("N0"); //Work(); } return 0; }