P3385 负环 • CoderXL's Blog

由于 Dijkstra 的贪心策略（它假设当前距离起点最近的节点，不可能通过其他路径变得更近），因此它不支持有负边的环。

另一方面，Bellman-Ford 和 Floyd 这两个基于动态规划的算法，不需要这个假设，因此适合处理有负边的环。

分析#

Bellman-Ford#

用于求解单源最短路。

每轮遍历所有边（也可以通过遍历所有点 + 遍历每个点的出边的方式实现），然后更新这条边直接相连的点到起点的距离，公式 dis[y] = min(dis[y], dis[x] + edge[x][y]).

如果图上存在最短路，那么一轮更新之后，当前求出的最短路的长度至少 $+1$ ，而最短路的长度最大为 $n-1$ ，因此最多遍历 $n-1$ 轮之后，图上任何边都不能缩短它指向的顶点到起点的距离了。

而，如果遍历 $n-1$ 轮之后，仍然存在能够更新点的边，那么必然说明形成了环。而只有在环是负环的时候，走过环的路程才会小于不走环的情况，因此可以判断有负环。

因此，通常的实践是，更新 $n$ 轮，并判断第 $n$ 轮有没有点被成功更新：

有 → 有负环
没有 → 没有负环

复杂度 $O(VE)$ .

Floyd#

Floyd 的算法流程和原理不再赘述，可见 B3647 的题解。此处简单提一下 Floyd 如何判断负环。

当 Floyd 进行完毕之后，如果存在 i，使得 dis[i][i]<0，就说明图上存在负环，且 i 自身就位于一个负环中；否则图上不存在负环。

当判断图上存在负环之后，标记在环上的点，然后所有能到达这些点的点，都是「能够从该点出发到达一个负环」的点。

复杂度 $O(V^3)$ .

代码#

本题数据范围需要使用 Bellman-Ford. 有一些坑点，比如：

无穷大不要赋值为 INT_MAX，可能导致加法溢出；
在松弛时务必单独判断某点的距离是否为无穷大，否则可能导致 $\infty > \infty - \mathrm{dis}[x][y]$ 从而误判更新（这种情况不应该更新）；
多测需要反复初始化；

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

int T;
int n,m;

struct Edge
{
    int x,y,w;
}edge[N<<1];
int cnt;
int dis[N];

void add(int x,int y,int w)
{
    cnt++;
    edge[cnt]={x,y,w};
}

void init()
{
    cnt=0;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++)
        {
            int x,y,w;
            cin>>x>>y>>w;
            if(w<0)
                add(x,y,w);
            else
            {
                add(x,y,w);
                add(y,x,w);
            }
        }
        bool flag=false;
        for(int i=1;i<=n;i++)
        {
            flag=false;
            for(int j=1;j<=cnt;j++)
            {
                // `w` can be negative, so it's required to
                // manually check if `dis` is INF
                    if(dis[edge[j].x]!=0x3f3f3f3f&&dis[edge[j].y]>dis[edge[j].x]+edge[j].w)
                {
                    dis[edge[j].y]=dis[edge[j].x]+edge[j].w;
                    flag=true;
                }
            }
            if(!flag)break;
        }
        if(flag==true)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

cpp