题解：P3385 【模板】负环

· · 题解

P3385 【模板】负环 题解

题目传送门

前置知识

图上最短路

在图这个数据结构中任意两点间会有路径相连（或是没有，此时则没有最短路），而这两点间的最短路就是指这些路径中最短的一条。

松弛

下面给出一个例子：

在一开始时，我们会对一个点进行其它所有点距离上限的估计。在这张图中，我们关注结点 s 和结点 v。
我们在一开始对于这两点的距离估计可能为 5。

当我们看到结点 u 时，会发现 s 到 u 的距离（即 2）再加上连接 u 与 v 的边的长度（即 1）会比我们一开始的估计的距离小，那么我们就可以用此更新我们估计的距离。
这种更新距离上限使其更接近于真实值的方式我们称作松弛。

换句话来说，就是用其它最短路的估计更新此最短路的估计，缩小它的范围。

SPFA 算法

SPFA（Shortest Path Faster Algorithm），便是求单源最短路的一种算法。

它有其优点：

但也有致命缺点：

实现方法

首先，我们建立一个队列，会在里面放入结点。在初始时队列中只会有起始点。
同时我们建立一个数组，记录该起始点到所有点的最短路径长度（所有值通常会被赋为一个极大值，而该点本身的值为 0）。

接着，我们取出队首的结点，对它所相连的结点进行判断是否能进行松弛操作。如果有结点被松弛了并且也没有在队列中，那么就把它放入队尾。

然后，重复上面的操作直到队列为空，这时我们就计算出了起始点到所有其它的点的最短路径长度。

下面给出代码：

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f; // 极大值
int dis[10005]; // 最短路径长度
struct node{
    int v,w;
}; vector <node> adj[10005];
bool in_q[10005]; // 结点是否在队列

void spfa(int s){ // 起点为 s
    memset(dis,INF,sizeof(dis)); // 初始化
    queue <int> q;
    dis[s] = 0,in_q[s] = 1,q.push(s); // 初始化起点
    while(!q.empty()){
        int h = q.front();
        in_q[h] = 0,q.pop(); // 更改该点的状态
        for(node x : adj[h])
            if(dis[x.v] > dis[h] + x.w){
                dis[x.v] = dis[h] + x.w; // 进行松弛
                if(!in_q[x.v]) // 不在队列
                    in_q[x.v] = 1,q.push(x.v); // 放入队列
            }
    }
}

在一般情况下，SPFA 算法的时间复杂度通常为 O(km)，其中 k 为一个常数，m 为边数。

但在稠密图边很多，或是被特殊的图卡时，会退化至 O(nm)。

详情可见： P3371 【模板】单源最短路径（弱化版）

题目分析

看到题目，我们可以想到在 SPFA 算法中，如果从一个起点能到达一个负环，由于结点会一直被松弛，我们就无法求出最短路，而是会重复地更新最短路长度。我们就要从这里突破。

判断负环

方法 1

在 SPFA 算法的基础上，我们再添加一个统计每个结点入队次数的数组。
如果一个点入队超过了 n 次（即图上结点个数），则判断有负环。

方法 2

我们统计每两个点间的最短路包含多少条边，如果在一条最短路上包含超过了 (n-1) 条边，说明有边被重复使用，则判断有负环。

正确性

在一开始初始化起始点时，我们其实是正确计算了从该点出发经过 0 条边的最短路。

可以知道，我们在第 k(k \ge 0) 次松弛操作后，就正确计算了所有从起始点出发，最多经过 k 条边的最短路。因此，在第 (k+1) 次松弛操作后，我们就可以正确计算所有从起始点出发，最多经过 (k+1) 条边的最短路。

在 (n-1) 次松弛操作后，最多经过 (n-1) 条边的最短路就被求出。
同时，从一个点到任意一点的最短路必然不会超过 (n-1) 条边。
所以方法 2 可行。

每个结点入队次数其实就是这个结点被松弛的次数。
所以如果在第 n 次松弛操作后仍然可以更新距离，则存在负环。
所以方法 1 可行。

代码实现

这里使用方法 2 实现判负环。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f; // 极大值
int T,n,m,q,dis[2005],cnt[2005]; // cnt 记录最短路径经过边数
bool in_q[2005];
struct node{
    long long v,w;
}; vector <node> adj[2005];

bool spfa(int s){
    memset(cnt,0,sizeof(cnt)); // 初始化计数数组
    queue <int> q;
    q.push(s),in_q[s] = 1,dis[s] = 0; // 初始化起点
    while(!q.empty()){
        int h = q.front();
        q.pop(),in_q[h] = 0;
        if(cnt[h] > n) // 判断最短路边数是否大于 n，通常会因为添加超级源点写为 > 而并非 >=
            return 1; // 有负环
        for(node x : adj[h])
            if(dis[x.v] > dis[h] + x.w){ // 可以松弛
                dis[x.v] = dis[h] + x.w; // 进行松弛
                cnt[x.v] = cnt[h]+1; // 边数为对它松弛的点的边数+1
                if(!in_q[x.v]) // 不在队中
                    in_q[x.v] = 1,q.push(x.v); // 入队
            }
    }
    return 0; // 成功计算出最短路，故没有负环
}

int main(){
    cin >> T;
    while(T--){
        memset(adj,0,sizeof(adj));
        memset(in_q,0,sizeof(in_q));
        memset(dis,INF,sizeof(dis));
    // 多测时包括图也要初始化！！！
        cin >> n >> m;
        while(m--){  // 建图
            int u,v,w;
            cin >> u >> v >> w;
            if(w >= 0)
                adj[u].push_back({v,w}),adj[v].push_back({u,w});
            else
                adj[u].push_back({v,w});
        }
        cout << (spfa(1)?"YES\n":"NO\n");
    }
    return 0;
}

上述代码时间复杂度为 O(nm)，在本题中可以通过。

拓展部分

本题只要求我们求“从点 1 出发能到达的负环”，当我们要求整个图时，我们需要考虑到图不一定为连通图，所以我们可以考虑增加一个超级源点 0。

这个超级源点会与所有节点间存在一条边权为 0 的单向边。

在开始时便以 0 号点为起点进行 SPFA，初始会将所有点加入队列，以完整地判断。

推荐练习

P1938 [USACO09NOV] Job Hunt S

总结

本题为负环模板题，考察图数据结构以及最短路算法，同时负环在差分约束系统中起重要作用。

感谢您的阅读！