spfa判负环

spfa判负环分为bfs和dfs两种。

dfs版的spfa是不稳定的，但在随机图上表现出色。

bfs版的复杂度为O(n*m),但是比较稳定。

能用bfs版的，就用bfs版的，如果bfs版的比较吃力，就用dfs版的。

如果有多组数据的话一定要把相关的数组初始化。

洛谷P3385 【模板】负环

bfs：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int N=2010;
int n,m,T,cnt,hd[N],dis[N],num[N];
bool inq[N];
struct edg{
    int nxt,to,w;
}e[N<<2];
inline void ins(int u,int v,int w){
    e[++cnt]=(edg){hd[u],v,w};
    hd[u]=cnt;
}
queue<int>q;
inline bool spfa(){
    memset(dis,0x7f,sizeof(dis));  
    memset(num,0,sizeof(num));
    q.push(1); dis[1]=0; inq[1]=1; num[1]=1;
    while(!q.empty()){
        int x=q.front(); q.pop(); inq[x]=0;
        for(int i=hd[x];i;i=e[i].nxt){
            int to=e[i].to;
            if(dis[to]>dis[x]+e[i].w){
                dis[to]=dis[x]+e[i].w;
                if(!inq[to]){
                    q.push(to); inq[to]=1;
                    if(++num[to]>=n) return 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    T=read();
    while(T--){
        n=read(); m=read();
        cnt=0; memset(hd,0,sizeof(hd));
        for(int i=1;i<=m;++i){
            int u=read(),v=read(),w=read();
            ins(u,v,w); if(w>=0) ins(v,u,w);
        }
        if(spfa()) printf("YE5
");
        else printf("N0
");
    }
    return 0;
}
    

dfs：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
inline void read(int &x){
    bool flag=0; x=0; char ch=getchar();
    while(ch<'0'||ch>'9'){flag=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=flag?~x+1:x;
}
int n,m,T,tot;
int head[maxn],dis[maxn]; bool vis[maxn];
struct node{
    int next,to,dist;
}e[maxn<<1];
inline void ins(int from,int to,int dist){
    e[++tot].next=head[from];
    e[tot].to=to; e[tot].dist=dist;
    head[from]=tot;
}
bool spfa(int x){
    vis[x]=true;
    for(int i=head[x];i;i=e[i].next)
    if(dis[e[i].to]>dis[x]+e[i].dist){
        if(vis[e[i].to]) return true;
        dis[e[i].to]=dis[x]+e[i].dist;
        if(spfa(e[i].to)) return true;
    }
    return vis[x]=false;
}
int main(){
    read(T);
    while(T--){
        tot=0; memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(dis,0,sizeof(dis));
        read(n);read(m);
        for(int i=1;i<=m;++i){
            int a,b,w; read(a);read(b);read(w);
            ins(a,b,w); if(w>=0) ins(b,a,w);
        }
        bool flag=0;
        for(int i=1;i<=n;++i)
        if(spfa(i)){
            flag=true;
            break;
        }
        if(flag) printf("YE5
");
        else printf("N0
");
    }
        return 0;
}