洛谷 P3385 【模板】负环 题解

时间:2023-03-10 06:59:25
洛谷 P3385 【模板】负环 题解

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

说明/提示

n\leq 2000n≤2000

m\leq 3000m≤3000

-10000\leq w\leq 10000−10000≤w≤10000

T\leq 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;
}