UVA 558 Wormholes：Bellman-Ford 判斷負環

題目簡介

給定 n 個星系（節點）和 m 個蟲洞（有向邊），每條邊有權值 t（可為負數，表示時間差）。判斷圖中是否存在負權環（即可無限回到過去）。多組測試資料，n ≤ 1000, m ≤ 2000。

解題思路

經典 Bellman-Ford 算法檢測負環：

1. 初始化距離數組 d[0]=0，其餘 INF。
2. 進行 n-1 輪鬆弛操作：對每條邊 (u, v, w)，若 d[u] + w < d[v] 則更新 d[v]。
3. 第 n 輪若仍能鬆弛任何邊，則存在負環，輸出 "possible"，否則 "not possible"。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXM = 2005;
const int INF = 0x3f3f3f3f;
int n, m;
int u[MAXM], v[MAXM], w[MAXM];
int d[MAXM];

bool bellmanFord() {
    fill(d, d+n, INF);
    d[0] = 0;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < m; j++) {
            if (d[u[j]] < INF && d[v[j]] > d[u[j]] + w[j])
                d[v[j]] = d[u[j]] + w[j];
        }
    }
    for (int j = 0; j < m; j++) {
        if (d[u[j]] < INF && d[v[j]] > d[u[j]] + w[j])
            return true; // 存在負環
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d %d %d", &u[i], &v[i], &w[i]);
        puts(bellmanFord() ? "possible" : "not possible");
    }
    return 0;
}

複雜度分析

時間複雜度 O(n×m)，空間複雜度 O(n+m)，滿足題目限制。