算法基础之SPFA判断负环

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");}