SPFA判断负环
-
核心思想:spfa算法 当遍历一个点时 cnt数组记录边数 若有负环 边数会无限+1 cnt>=n是即为有负环
-
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 2010 , M = 10010; int h[N], e[M] , ne[M] , w[M] , idx; int d[M] , cnt[N]; int n,m; bool st[N]; void add(int a,int b,int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++; } bool spfa() { //不用初始化d,只要确定d更新了即可 queue<int> q; for(int i=1;i<=n;i++) { st[i] = true; q.push(i); //把每个点都放进去 因为不一定是从1开始的回路 可能是从2开始的不全是负值的环 //如果不放:只能求出从1开始的负环 } 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(d[j] > d[t] + w[i]) { d[j] = d[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); while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } if(spfa()) puts("Yes"); else puts("No"); }
-