Description

给定一个有向图 \(G\) ，求 \(G\) 中是否存在负环。

Solution

既然这道题让我们要判断负环，那么我们肯定不能用 Dijkstra 了。但是，我们可以使用 Floyd 或 Bellman-Ford 算法来处理负权边。

Floyd 固然好写，但是数据范围限制了它：\(1 \leqslant n \leqslant 10^3\) 。所以，我选用了时间复杂度较优的 Bellman-Ford 算法 （因为它没死）。

Bellman-Ford 算法的主体部分我就不详细说了，主要来说说如何判断负环。

根据定义，Bellman-Ford 算法会在至多 \(n - 1\) 次后完成所有的松弛操作，即执行完 Bellman-Ford 的主体部分后得出的结果数组就应当是最短路。

所以，我们可以在执行完 Bellman-Ford 算法后再去尝试进行松弛操作。此时，如果存在负环，那么一定可以继续松弛。反之，如果所有边都无法继续松弛，那么这个图不存在负环。

Code

#include <iostream>
#include <memory.h>
using namespace std;
const int MAXN = 1e3 + 10, MAXM = 2 * 1e3 + 10;

struct edge {
    int u, v, w;
};

edge e[MAXM];
int dis[MAXN];
int n, m, x, y, t;

void bellman_ford() {  // Bellman-Ford 主体部分
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (dis[e[j].v] >= dis[e[j].u] + e[j].w) {  // 松弛操作
                dis[e[j].v] = dis[e[j].u] + e[j].w;
            }
        }
    }
}

bool check_negative_cycle() {  // 检查是否存在负环
    for (int i = 1; i <= m; i++) {  // 循环每个边
        if (dis[e[i].v] > dis[e[i].u] + e[i].w) return 1;  // 如果仍然能够松弛，则代表有负权环存在
    }
    return 0;
}

void initialize() {  // 初始化
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;  // 从太阳系（点0）出发
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
        bellman_ford();  // 先跑一遍Bellman-Ford
        if (check_negative_cycle()) cout << "possible" << endl;  // 然后检查有没有负权环
        else cout << "not possible" << endl;
    }
    return 0;
}