POJ 2983 差分約束系統求解 - SPFA 判斷負環完整實現

統一轉化為 xⱼ - xᵢ ≤ w 形式，建立有向邊 i → j 權重 w。系統有解 ⇔ 圖中無負環。

SPFA 判負環核心代碼

const int MAXN = 1010;
struct Edge { int to, w, next; } E[MAXN*200];
int head[MAXN], ecnt;
int dis[MAXN], cnt[MAXN];
bool inq[MAXN];

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

bool spfa(int n) {
    queue q;
    fill(dis, dis+n+1, 0);      // 超級源點 0 連向所有點，初始距離 0
    fill(cnt, cnt+n+1, 0);
    fill(inq, inq+n+1, true);
    for (int i = 1; i <= n; ++i) q.push(i); // 全點入隊，處理非連通圖

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (int e = head[u]; ~e; e = E[e].next) {
            int v = E[e].to, w = E[e].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (++cnt[v] > n) return false; // 第 n+1 次鬆弛 → 負環
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
    return true; // 無負環
}

關鍵技巧總結

1. 超級源點 0：對每個 i 加邊 0→i 權重 0，等價於將所有點初始入隊，保證非連通圖也能檢測負環。
2. 計數器 cnt[v]：記錄 v 入隊/鬆弛次數，超過 n 次即證明存在負環（貝爾曼-福德定理）。
3. 邊構建細節：P 條件拆兩條邊，V 條件一條邊，注意方向與符號。

複雜度分析

• 時間：平均 O(kE)，k 為平均鬆弛輪數，實測極快；最差 O(VE) 但隨機數據難觸發。
• 空間：O(V+E)。

對比：Bellman-Ford vs SPFA