【模板】负环

洛谷P3385 【模板】负环

模板题没人发题解嘛？？大概是太简单了dalao们不屑于发吧（大雾，轻喷）

前言

确实很模板，题意清晰明了，下面给出\(Bellman-Ford\)算法判定负环和\(SPFA\)判定负环这两种做法的讲解qwq

（为了学好差分约束来的）

\(SPFA\)判定负环

• 设\(cnt[i]\)表示从\(1\)到\(i\)的最短路径包含的边数，\(cnt[1]=0\)

当执行更新\(dis[v]=dis[x]+e[i].val\)时，同时更新\(cnt[v]=cnt[x]+1\)

若发现\(cnt[v]≥n\)，则说明图中又负环；若算法正常结束，则说明图中没有负环

• 设\(cnt[i]\)表示从\(1\)到\(i\)的最短路径上每个点入队的次数，\(cnt[1]=0\)

当执行更新\(dis[v]=dis[x]+e[i].val\)时，同时更新\(cnt[v]++\)

若\(cnt[v]==n\)则说明有负环

• 关于这两种方法的效率

《算法竞赛进阶指南》上说第一种方法比第二种方法高效：因为第一种方法只需要绕环一次就能发现负环，而判定入队次数的做法需要绕环\(n\)次

\(However\)，我针对于这两种方法都交上去评测，结果大出意料：第二种方法成功AC，然后第一种方法只有\(10pts\)！（大概是我没编对？如果您做出来能够AC，可否麻烦您贴一下代码，谢谢啊qwq）

• 代码\(Code\)

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int T,n,m,u,v,w;
int tot,dis[60010],vis[60010],cnt[60010],head[60010];

struct node {
    int to,net,val;
} e[60010];

inline void add(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].net=head[u];
    head[u]=tot;
}

inline bool spfa() {
    for(register int i=1;i<=n;i++) {
        vis[i]=0;
        cnt[i]=0;
        dis[i]=20050206;
    }
    dis[1]=0;
    vis[1]=0;
    cnt[1]++;
    q.push(1);
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(register int i=head[x];i;i=e[i].net) {
            int v=e[i].to;
            if(dis[v]>dis[x]+e[i].val) {
                if(cnt[v]>=n-1) return true;  //判定入队次数
                dis[v]=dis[x]+e[i].val;
                if(!vis[v]) {
                                        cnt[v]++;
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        tot=0;
        for(register int i=1;i<=n;i++) {
            e[i].to=0;
            e[i].val=0;
            e[i].net=0;
            head[i]=0;
        }
        scanf("%d%d",&n,&m);
        for(register int i=1;i<=m;i++) {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        if(spfa()==false) puts("NO");
        else puts("YES");
    }
    return 0;
}

\(Bellman-Ford\)判定负环

• 如何判定负环

若经过\(n\)轮迭代，算法仍未结束（仍有能产生更新的边），则图中存在负环

若\(n-1\)轮迭代之内，算法结束（所有边都满足三角形不等式），则图中无负环

• 本题注意

本题需要注意一点的是：题目要求找到一个 \(1\)能到达的负环

而输入并不保证\(1\)一定与其他点连通！即\(1\)可能是一个“孤儿点”（#11就是一个例子QAQ）

• 代码\(Code\)

#include <bits/stdc++.h>
using namespace std;
int T,n,m,u,v,w,tot,flag,dis[600010];

struct node {
    int to,fro,val;
} e[600010];

inline void add(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].fro=u;
    e[tot].val=w;
}

inline bool ford() {
    for(register int i=1;i<=n;i++) dis[i]=2005020600;
    dis[1]=0;
    for(register int i=1;i<n;i++) {
        for(register int j=1;j<=tot;j++) {
            if(dis[e[j].fro]+e[j].val<dis[e[j].to]) {
                dis[e[j].to]=dis[e[j].fro]+e[j].val;
            }
        }
    }
    for(register int i=1;i<=tot;i++) {
        if(dis[e[i].fro]+e[i].val<dis[e[i].to]) return true;
    }
    return false;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        tot=0;flag=0;
        scanf("%d%d",&n,&m);
        for(register int i=1;i<=m;i++) {
            scanf("%d%d%d",&u,&v,&w);
            if(u==1||v==1) flag=1;
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        if(flag==0) {
            puts("NO");
            continue;
        } 
        if(ford()==false) puts("NO");
        else puts("YES");
    }
    return 0;
}

最后，如果您有任何不懂或这篇题解有任何不对的地方，欢迎评论区指出，我会及时回复、改正，谢谢各位dalao阅读qwq