P3385 【模板】负环
题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
寻找一个从顶点1所能到达的负环，负环定义为：一个边权之和为负的环。
输入格式
第一行一个正整数T表示数据组数，对于每组数据：
第一行两个正整数N M，表示图有N个顶点，M条边
接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）
输出格式
共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。
输入输出样例
输入 #1
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出 #1
N0
YE5
说明/提示
nleq 2000n≤2000
mleq 3000m≤3000
-10000leq wleq 10000−10000≤w≤10000
Tleq 10T≤10
建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造，请不要使用玄学算法 本题数据有更
【思路】
SPFA判负环
有点想喷这个题
为什么输出YE5和N0
注意这里是YE 和 5（数字5不是S）
N 和 0(数字0不是O)
这就很坑人了吧
一般粗心一点的人就会情不自禁的写上了YES和NO（字母版）
然后就gg
会不会是出题人出不出来难题就那这个东西来恶心人QWQ
【题目分析】
多个图判断有没有负环
【核心思路】
根据题目给出的要求建一个图
然后用SPFA开始跑
前面出现了几个点
用一个计数器记录每个点前面出现了几个点
也就是这个点到前面走过来的链
如果这条链的长度大于了n
超出了点数
那就证明重复走了某些点
SPFA重复走
这就可以说明出现了负环
然后输出YE5就好了
如果没有重复走
那就输出N0
SPFA判负环的详情解释请见
这里
【注意】
每次建图之前要先把前面的东西清空一下下
然后
再说一遍输出YE5和N0
【完整代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int Max = 3010;
const int MMax = 2010;
struct node
{
int y,ne,z;
}a[Max << 1];
int sum = 0;
int head[MMax];
void add(int x,int y,int z)
{
a[++ sum].y = y;
a[sum].ne = head[x];
a[sum].z = z;
head[x] = sum;
}
int n,m;
bool use[MMax];
int d[MMax],cnt[MMax];
bool SPFA()
{
memset(cnt,0,sizeof(cnt));
memset(use,false,sizeof(use));
for(register int i = 1;i <= n;++ i)
d[i] = 999999999;
d[1] = 0;
queue<int>q;
q.push(1);
while(!q.empty())
{
int qwq = q.front();
q.pop();use[qwq] = false;
for(register int i = head[qwq];i != 0;i = a[i].ne)
{
int awa = a[i].y;
if(d[awa] > d[qwq] + a[i].z)
{
d[awa] = d[qwq] + a[i].z;
cnt[awa] = cnt[qwq] + 1;
if(cnt[awa] > n)
return false;
if(use[awa] == false)
{
use[awa] = true;
q.push(awa);
}
}
}
}
return true;
}
signed main()
{
int t;
t = read();
while(t --)
{
n = read(),m = read();
sum = 0;
int a,b,w;
memset(head,0,sizeof(head));
for(register int i = 1;i <= m;++ i)
{
a = read();b = read();w = read();
add(a,b,w);
if(w >= 0)
add(b,a,w);
}
if(SPFA() == true)
cout << "N0" << endl;
else
cout << "YE5" << endl;
}
return 0;
}