仓山网站建设/网站首页快速收录

一道判断负环的模板题。

这里主要介绍三种判断负环的方法。

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;
}