HDU 3592 World Exhibition - 差分約束系統與 SPFA 判斷負環

題目建模

給定 n 個變數 S₁...S_n，兩類約束：

• x 條 Sb - Sa ≤ c → 有向邊 a → b 權重 c
• y 條 Sa - Sb ≤ -c → 有向邊 b → a 權重 -c

目標：求 S₁ 到 S_n 的最短路徑（即 S_n - S₁ 的最大可能值）。

核心判斷邏輯

1. 負環存在（SPFA 計數超 n） → 輸出 -1（系統不一致）。
2. 1 號點無法到達 n 號點（d[n] == INF） → 輸出 -2（關係不確定）。
3. 正常可達 → 輸出 d[n]（最短距離）。

圖構建技巧：虛擬源點

為處理不連通圖，標準做法：

• 新增超級源點 0，向所有點連邊權 0。
• 或初始將所有點入隊、距離設 0（本題代碼採用此法）。

確保 SPFA 能遍歷所有連通分量，正確檢測任意位置的負環。

SPFA 關鍵實作細節

int spfa(int s) {
    memset(d, 0x3f, sizeof d); // INF
    memset(inq, 0, sizeof inq);
    memset(cnt, 0, sizeof cnt); // 入隊次數
    d[s] = 0; inq[s] = 1;
    queue<int> q; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        if (++cnt[u] > n) return 0; // 負環檢測
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    return 1;
}

完整參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 30020;

struct Edge { int v, w, next; } e[MAXM];
int head[MAXN], ecnt, n, d[MAXN], inq[MAXN], cnt[MAXN];

void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

bool spfa() {
    memset(d, 0, sizeof d); // 所有點距離初始 0
    memset(inq, 1, sizeof inq); // 全部入隊
    memset(cnt, 0, sizeof cnt);
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
                if (++cnt[v] > n) return false; // 負環
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int x, y; cin >> n >> x >> y;
        memset(head, -1, sizeof head); ecnt = 0;
        while (x--) { int a,b,c; cin>>a>>b>>c; addEdge(a,b,c); }
        while (y--) { int a,b,c; cin>>a>>b>>c; addEdge(b,a,-c); }
        if (!spfa()) cout << "-1\n";
        else if (d[n] < INF/2) cout << d[n] << '\n';
        else cout << "-2\n";
    }
    return 0;
}

複雜度與優化

• SPFA 平均 O(k·E)，k 為平均鬆弛輪數，實測極快。
• 可用 SLF/LLL 優化隊列順序，但本題規模 (n≤1000) 基礎版足夠。
• 注意 INF 設定避免溢位：0x3f3f3f3f 加權不會溢出 int。

易錯點總結

• ❌ 忘記反向邊權重取負（Sa-Sb≤-c → b→a (-c)）。
• ❌ 未處理不連通情況導致誤判 -2。
• ❌ 負環檢測用 cnt[v] > n 而非 > n+1（含虛擬源點時才需 n+1）。