您的位置:首页 > 汽车 > 新车 > 【AcWing】852. spfa判断负环

【AcWing】852. spfa判断负环

2025/2/1 4:25:27 来源:https://blog.csdn.net/Wheattail/article/details/142005704  浏览:    关键词:【AcWing】852. spfa判断负环

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;const int N= 1e5+10;int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[N];//cnt存最短路径的边数
bool st[N];void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;  
}int spfa(){//不需要初始化,求的不是距离1号点的最短路径,而是是不是存在负环。//memset初始化作用于的是求起点到终点的最短路径,而判读负环只依靠dist[j]>dist[t]+w[i]递推就可以判断。//dist只是工具数组,初值是多少都无所谓,dist不断变小才是关键。//把所有顶点都入队了,可以看成所有点都是初始点。//在第一步每个点都作为初始点走下一步时,下一步如果是正权值,那压根就不会走,下一步是负权值才会走。由于负权回路总和是负数,所以就算下一步是正权值,由前几步积累的负值的绝对值肯定会大于这个值,然后加完为负数,就能走了。一直无限循环,直到积累的边数达到判断条件。/*memset(dist,0x3f,sizeof dist);dist[1]=0;*/queue<int> q;//不能把1号点放进去,题目判断是否存在负环,并不是判断是否存在从1开始的负环。就是可能存在1号点到不了的负环。//那怎么办呢?把每个点都放到初始的点集里面。这样只要存在负环的话,就一定可以找到。for(int i=1;i<=n;i++){q.push(i);st[i]=true;}while(q.size()){int t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n) return true;if(!st[j]){q.push(j);st[j]=true;}}}}return false;
}int main(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);}if(spfa()) puts("Yes");else puts("No");return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com