题目描述
暴力枚举/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+7; int n,m,T,size,in[N]; int head[N],dis[N]; bool vis[N],kaka; int team[N<<3],h,t; struct Node{ int to,val,next; }edge[N<<1]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } void ready() { memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); memset(dis,37,sizeof(dis)); memset(in,0,sizeof(in)); kaka=false;size=0; } 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=0,t=1;team[h]=sta; dis[sta]=0;vis[sta]=true;in[sta]++; while(h<t){ int x=team[h++];vis[x]=false; for(int i=head[x];i!=-1;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=1;i<=m;i++){ int x=read(); int y=read(); int z=read(); add(x,y,z); if(z>0)add(y,x,z); } spfa(1); if(kaka)printf("YE5 "); else printf("N0 "); } return 0; }