题解：P3385 【模板】负环

niu_zh · 2025-04-29 20:25:01 · 题解

思路

负环就是有向图上一个边权之和是负数的环。

我们通常使用 Bellman-Ford 及其衍生算法 SPFA 解决此问题。

由于 SPFA 并没有在最差情况下比 Bellman-Ford 快，并且每一个大赛出题人都应该知道如何卡掉常见的 SPFA，所以并不建议使用 SPFA 替代 Bellman-Ford，如果 Bellman-Ford 都跑不过去就应该更换思路。你用来骗分当我没说。

想要了解 Bellman-Ford 就要先了解松弛操作。

对于边权为 w 的边 (u,v)，松弛操作对应这个式子：dis_v=\min(dis_v,dis_u+w)。

这么做的含义就是尝试用 S\rightarrow u \rightarrow v（箭头代表已知最短路径）这条路去更新 v 的最短路径长度。如果更优，就更新。

而 Bellman-Ford 就是不断对图上每一条边进行松弛。每一次循环，都对所有边进行一次松弛操作。

所以当最短路存在时，需要循环多少次呢？

当最短路存在时，每一次松弛操作都会让最短路长度加一，而最短路长度最长为 n-1。所以最多做 n-1 轮松弛操作。时间复杂度是 O(nm)。

注意，是在最短路存在时最多需要 n-1 轮松弛操作。而当图里有负环时，最短路是不存在的，因为只要已知绕着负环转，最短路就会到负无穷。所以如果在第 n 轮还能进行松弛，图上就存在能从源点到的负环。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
vector<pair<int,int>> mp[N];//图
int dis[N];//最短路长度。
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int n,m;
        cin>>n>>m;
        for (int i=1; i<=n; i++)
        {
            mp[i].clear();
        }
        for (int i=1; i<=m; i++)//输入图。
        {
            int u,v,w;
            cin>>u>>v>>w;
            mp[u].push_back({v,w});
            if(w>=0)
            {
                mp[v].push_back({u,w});
            }
        }
        memset(dis,0x3f,sizeof(dis));//初始正无穷。
        dis[1]=0;//源点距离是0。
        for (int i=1; i<n; i++)
        {
            bool flag=false;
            for (int j=1; j<=n; j++)
            {
                for (auto it:mp[j])
                {
                    if (dis[j]!=0x3f3f3f3f&&dis[it.first]>dis[j]+it.second)//进行松弛。
                    {
                        dis[it.first]=dis[j]+it.second;
                        flag=true;
                    }
                }
            }
            if (!flag)//不能再松弛。
            {
                break;
            }
        }
        bool flag=false;
        for (int i=1; i<=n; i++)
        {
            for (auto it:mp[i])
            {
                if (dis[i]!=0x3f3f3f3f&&dis[it.first]>dis[i]+it.second)
                {
                    flag=true;//有负环。
                    break;
                }
            }
            if (flag)
            {
                break;
            }
        }
        if (flag)
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
    }
    return 0;
}