[模板]SPFA判负环

目录

• 一、BFS法判负环
• 二、DFS法判负环
• 三、SPFA判正环

---

一、BFS法判负环

Code：

#include<bits/stdc++.h>
#define re register
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int first[8000],next[8000],go[8000],tot,cost[8000];
int dist[8000],vis[8000],add[8000];
inline void add_edge(int u,int v,int w){
    next[++tot]=first[u];
    first[u]=tot;
    go[tot]=v;cost[tot]=w;
}
inline void read(int &x){
    x=0;int flag=1;char ch=getchar();
    while(isdigit(ch)){if(ch=='-') flag=-1;ch=getchar();}
    while(!isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=flag;
}
int SPFA(){
    queue<int> q;
    for(int i=1;i<=n;i++){dist[i]=INF;vis[i]=0;}
    dist[1]=0;vis[1]=1;q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();vis[u]=0;
        for(int e=first[u];e;e=next[e]){
            int v=go[e],w=cost[e];
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                add[v]++;               //核心代码
                if(add[v]>n) return 1;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 0;
}
int main()
{
    read(n),read(m);
    for(re int i=1;i<=m;i++){
        int u,v,w;
        read(u),read(v),read(w);
        add_edge(u,v,w);
    }
    if(SPFA()) printf("YES\n");
    else printf("NO\n");
    return 0;
}

二、DFS法判负环

给出主体部分，其余部分与上一个代码类似。
Code：

int SPFA(int u)
{
    vis[u]=1;
    for(int i=first[u];i;i=next[i])
    {
        int v=go[i],w=cost[i];
        if(dist[v]>dist[u]+w)
        {
            dist[v]=dist[u]+w;
            if(vis[v]||SPFA(v)){
                vis[v]=0;
                return 1;
            }
        }
    }
    vis[u]=0;
    return 0;
}

三、SPFA判正环

1. 由原来的最短路改为最长路
2. 将权值变为原来的相反数并跑最短路判负环

---