题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式：
第一行一个正整数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
分析：一般来说，dfs判负环比bfs要快，但本来dfs的spfa就是指数级的复杂度，因此卡数据的话会死的比bfs还惨（亲身体会）。所以实际上用bfs判负环写的好的话不太会被卡（当然，故意卡bfs的题这话你当我没讲）。然后，小蒟蒻写了一份bfs的判负环放洛谷上，被卡常卡了一个小时。。。真的可怕。。。（这数据简直丧心病狂。。。）
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+;
int n,m,T,size,in[N];
int head[N],dis[N];
bool vis[N],kaka;
int team[N<<],h,t;
struct Node{
int to,val,next;
}edge[N<<];
inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
}
void ready()
{
memset(head,-,sizeof(head));
memset(vis,false,sizeof(vis));
memset(dis,,sizeof(dis));
memset(in,,sizeof(in));
kaka=false;size=;
}
inline void add(int x,int y,int z)
{
edge[++size].to=y;
edge[size].val=z;
edge[size].next=head[x];
head[x]=size;
}
void spfa(int sta)
{
h=,t=;team[h]=sta;
dis[sta]=;vis[sta]=true;in[sta]++;
while(h<t){
int x=team[h++];vis[x]=false;
for(int i=head[x];i!=-;i=edge[i].next){
int y=edge[i].to;
if(dis[x]+edge[i].val<dis[y]){
if(++in[y]>=n){kaka=true;return;}
dis[y]=dis[x]+edge[i].val;
if(!vis[y]){
team[++t]=y;vis[y]=true;
}
}
}
}
}
int main()
{
T=read();
while(T--){
n=read();m=read();
ready();
for(int i=;i<=m;i++){
int x=read();
int y=read();
int z=read();
add(x,y,z);
if(z>)add(y,x,z);
}
spfa();
if(kaka)printf("YE5\n");
else printf("N0\n");
}
return ;
}