判断一张图中是否存在关于顶点1的负环:
可以用SPFA跑一遍，存在负环的情况就是点进队大于n次
因为在存在负环的情况下,SPFA会越跑越小，跑进死循环
在最差的情况下,存在的负环长度是“n+1个顶点”这么长
rt:
显然这是n个点长度,但不是环；
这就是一个环,n+1个点的长度;
所以代码很明了了,只需将一般SPFA改动一点饥渴
CODE:
#include<bits/stdc++.h>万能头，懒得打很多头文件 using namespace std; //数据是骗人的，要开大.. const int maxn=50001; //基本的变量或者数组都是： queue<int > q; bool visited[maxn]; int head[maxn],cnt,js[maxn],dis[maxn]; struct ppap { int next,to,dis; } edge[maxn]; int t,n,m; //快读部分 int read() { bool f=0; char ch; int x=0; ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=!f; ch=getchar(); } while(ch<='9'&&ch>='0') { x=x*10+ch-'0'; ch=getchar(); } return !f?x:-x; } //链式前向星添边 void add(int from,int to,int dis) { edge[++cnt].next=head[from]; head[from]=cnt; edge[cnt].to=to; edge[cnt].dis=dis; } //和常见spfa一样，在其中判断条件即可 bool SPFA() { q.push(1); visited[1]=1; dis[1]=0; js[1]=1; while(!q.empty()) { int u=q.front(); q.pop(); visited[u]=0; for(int i=head[u]; i; i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; if(visited[v]==0) { js[v]=js[u]+1; if(js[v]>n) return true; visited[v]=1; q.push(v); } } } } return false; } int main() { t=read(); while(t--) { n=read(),m=read(); memset(head,0,sizeof head); memset(js,0,sizeof js); memset(edge,0,sizeof edge); memset(dis,0x3f,sizeof dis); memset(visited,0,sizeof visited); //初始化 for(int i=1,a,b,w; i<=m; i++) { a=read(),b=read(),w=read(); add(a,b,w); if(w>=0) add(b,a,w); } if(SPFA()) cout<<"YE5"<<" "; else cout<<"N0"<<" "; } return 0;//平淡的结束 }