一、题意

农夫有n块田地, 编号 1...n(1<=N<=500)，田地间有m1条双向路径，每条路径有一个经过所需要的时间wi。同时有m2个单向虫洞, 每条虫洞走完后时间倒回wi。
问农夫是否能在田地中遇到以前的自己。

二、解析

  • 这道题的情景非常有意思，m1条双向路径的权值为w，而m2条虫洞则相当于单向的负权路径，这样题目实际上就是判断图中是否存在负环，若存在，则农夫可以沿着负环一直走，时间将一直倒退，直到遇到以前的自己😀.

  • 带负权的最短路径问题，可以使用Bellman-Ford或它的优化版本，即spfa算法。spafa算法能解决带负权的单源最短路问题，同时判断是否存在负环。最坏时间复杂度为O(nm)。比Dijkstra慢，因此对于正权的单源最短路我们使用Dijkstra，而对于带负权的就只能使用spfa算法了。

  • spfa算法的原理：先从Bellman-Ford算法的原理开始，Bellman-Ford算法通过将每条边松弛n-1次来求出每个点的最终d[maxn]，即松弛到不能再松弛了。而如果第n次还存在边可以继续松弛，说明存在负环。而spfa通过让已经松弛得不能再松弛的边不再入队来实现减少冗余的松弛操作，用队列来存储每一轮迭代后还需要继续松弛的边，就是这样一个优化。

spfa的模板与Dijkstra有点像，需要注意区分。

三、代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 500 + 5, INF = 1 << 30;
struct edge {
    int to, w;
    edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int kase, n, m1, m2, d[maxn], inq[maxn], cnt[maxn];

bool spfa(int s) {
    fill(d, d + n + 1, INF); d[s] = 0;
    fill(inq, inq + n + 1, 0);
    fill(cnt, cnt + n + 1, 0);
    queue<int> que;
    que.push(s), inq[s] = 1, ++ cnt[s];
    while(!que.empty()) {
        int u = que.front(); que.pop();
        inq[u] = 0;  // 可以重复入队
        for(int i = 0; i < G[u].size(); i ++) {
            const edge& e = G[u][i];
            if(d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                que.push(e.to), inq[e.to] = 1;
                if(++ cnt[e.to] > n) return 1;  // 入队超过n次说明有负环
            }
        }
    }
    return 0;
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> m1 >> m2;
        for(int i = 1; i <= n; i ++) G[i].clear();
        while(m1 --) {
            int u, v, w;
            cin >> u >> v >> w;
            G[u].push_back(edge(v, w));
            G[v].push_back(edge(u, w));
        }
        while(m2 --) {
            int u, v, w;
            cin >> u >> v >> w;
            G[u].push_back(edge(v, -w));
        }
        cout << (spfa(1) ? "YES" : "NO") << endl;
    }
}

四、归纳

  • spfa算法用于解决带负权的单源最短路问题，同时可以判断负环，其模板如下： 
struct edge {  // 用于存图的edge结构
    int to, w;
    edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int n, m, inq[maxn], cnt[maxn], d[maxn];

bool spfa(int s) {
    fill(d, d + n + 1, INF); d[s] = 0;
    fill(inq, inq + n + 1, 0);  // inq用于标记每个点是否在队列中
    fill(cnt, cnt + n + 1, 0);  // cnt用于统计每个点的入队次数
    queue<int> que;  // 只需要使用普通队列
    que.push(s), inq[s] = 1, ++ cnt[s];
    while(!que.empty()) {
        int u = que.front(); que.pop();
        inq[u] = 0;  // 可以重复入队
        for(const edge& e : G[u]) {
            if(d[e.to] > d[u] + e.w) {  // 松弛操作
                d[e.to] = d[u] + e.w;
                que.push(e.to), inq[e.to] = 1;
                if(++ cnt[e.to] > n) return 1;  // 入队超过n次说明有负环
            }
        }
    }
    return 0;
}

int main() {
    ......
    spfa(1);
    ......
}
  • 要注意区分Dijkstra模板和spafa模板：
    • Dijkstra使用优先队列，spfa使用普通队列
    • Dijkstra使用vis数组排出重复点；spfa使用inq记录是否在队列中，用cnt记录入队次数，允许重复入队
  • 若原图不连通，需要加一个点使得原图连通后再用spfa算法来判断负环，否则会漏判。