本文共 1466 字，大约阅读时间需要 4 分钟。

判断负环

题目链接：

题目大意

就是求一个图中有没有负环。

思路

这题好奇怪啊。

先不说代码部分，就输出的内容。

这个就算了，判断负环我们用 SPFA 来判，我用的是看入队次数。那任意一个点入队次数大于等于 $n$ 的时候就有负环吧。

好，那我们看正确代码。luogu 上也有这道题，但是 YES 和 NO 是正常输出，好我们对了标发现每区别，结果把标丢上去也是 $55$ 分？！

后来玄学一顿乱改，结果 A 了。

代码

#include
   
    #include
    
     #include
     
      using namespace std;struct node {   	int x, to, nxt;}e[6001];int T, x, y, z, KK;int n, m, le[2001];int num[2001], dis[2001];bool in[2001];queue 
      
        q;void add(int x, int y, int z) {   	e[++KK] = (node){   z, y, le[x]}; le[x] = KK;}bool work() {   	dis[1] = 0;	in[1] = 1;	num[1] = 1;	q.push(1);	while (!q.empty()) {   		int now = q.front();		q.pop();				for (int i = le[now]; i; i = e[i].nxt)			if (dis[now] + e[i].x < dis[e[i].to]) {   				dis[e[i].to] = dis[now] + e[i].x;				if (!in[e[i].to]) {   					in[e[i].to] = 1;					q.push(e[i].to);					num[e[i].to]++;					if (num[e[i].to] >= n - 1) return 1;				}			}				in[now] = 0;	}		return 0;}int main() {   	scanf("%d", &T);	for (int times = 1; times <= T; times++) {   		memset(le, 0, sizeof(le));		memset(num, 0, sizeof(num));		memset(dis, 0x7f, sizeof(dis));		KK = 0;				scanf("%d %d", &n, &m);				for (int i = 1; i <= m; i++) {   			scanf("%d %d %d", &x, &y, &z);			add(x, y, z);			if (z >= 0) add(y, x, z);		}				if (work()) printf("YE5\n");			else printf("N0\n");	}		return 0;}