题解 P3385 【【模板】负环】

· · 题解

判断负环

若图中存在一个环，环上各边的边权和为负数，则称该环为负环。

含有负环的图显然是没有最短路的，因为每走一次这个负环，总权值就会更小，导致陷在环里出不来。

我们可以用 Bellman-Ford 或 SPFA 来判断负环。

Bellman-Ford 判断负环

Bellman-Ford 算法通过不断迭代计算最短路，每轮迭代至少有一个结点得到了最短路。所以，若图中没有负环，则最多经过 n-1 轮迭代后算法结束。若第 n 轮迭代仍有结点的最短路能被更新，则图中有负环。复杂度为 O(nm)。

SPFA 判断负环

SPFA 是队列优化的 Bellman-Ford，所以我们可以类比 Bellman-Ford 判断负环。然而 SPFA 使用队列，无法直接得知在进行第几轮迭代。再观察 Bellman-Ford，我们发现第 i 轮迭代实际是在计算最短路包含 i 条边的结点。所以我们用 cnt[x] 表示 1 到 x 的最短路包含的边数，cnt[1]=0。每次用 dis[x]+w(x,y) 更新 dis[y] 时，也用 cnt[x]+1 更新 cnt[y]。此过程中若出现 cnt[y]\ge n，则图中有负环。最坏情况复杂度也是 O(nm)。

也可以用另一种方式理解：1 到 x 的最短路上的边数一定不多于 n-1。否则至少有一个结点被重复经过，这说明存在环，且经过该环能更新该结点的 dis 值，即存在负环。

SPFA 也可以通过记录每个点的入队次数判断负环，若有节点入队次数 \ge n，则有负环。这种方式效率会略低。可以参考其他题解。

下面的代码中，利用了 SPFA 记录最短路经过边数的方法判负环。

#include<cstdio>
#include<cstring>
const int maxn=2e3+10;
const int maxm=6e3+10;
int n,m;
struct Edge{
    int to,w,next;
}edge[maxm];        //链式前向星存图
int head[maxn],tot;
inline void Init(){     //有多组测试数据，每次初始化
    for(int i=0;i<maxm;i++) edge[i].next=0;
    for(int i=0;i<maxn;i++) head[i]=0;
    tot=0;
}
inline void addedge(int u,int v,int w){
    edge[++tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot;
}
#include<queue>
using std::queue;
queue<int> Q;
int dis[maxn],vis[maxn],cnt[maxn];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[1]=0; vis[1]=true;
    Q.push(1);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        vis[x]=false;
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].to,z=edge[i].w;
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;  //更新最短路
                cnt[y]=cnt[x]+1;  //更新包含边数
                if(cnt[y]>=n) return true;  //判定存在负环
                if(!vis[y]){
                    Q.push(y);
                    vis[y]=true;
                }
            }
        }
    }
    return false;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        Init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            if(w>=0) addedge(v,u,w);
        }
        puts(spfa()?"YES":"NO");
    }
    return 0;
}