POJ 3169 Layout：差分約束系統與 Bellman-Ford/SPFA 完全攻略

題目建模：差分約束系統

設 x[i] 為第 i 頭牛的位置坐標。約束轉化為：

• ML 組 x[v] - x[u] ≤ w（距離 ≤ w） → 有向邊 u → v 權 w
• MD 組 x[u] - x[v] ≤ -w（距離 ≥ w） → 有向邊 v → u 權 -w
• 順序約束 x[i] - x[i+1] ≤ 0 → 有向邊 i+1 → i 權 0

求 max(x[n] - x[1])。
令 x[1] = 0（源點），則 x[n] 的最短路即為最大距離（最短路使所有變量在滿足約束下取得最大值）。

三種輸出情況

1. 負權環存在 → 約束衝突，無解，輸出 -1。
2. 無負權環但 x[n] = INF → 1 號牛與 n 號牛不連通，距離可無限大，輸出 -2。
3. 正常有解 → 輸出 dis[n]（最短路距離）。

算法選擇：SPFA 優於 Bellman-Ford

邊數 ML + MD + n ≤ 20000 + 1000，節點 n ≤ 1000。
Bellman-Ford O(VE) 邊界較緊，SPFA 平均 O(E) 更快。
關鍵技巧：為檢測與源點不連通的負環，初始將所有節點入隊（或加超級源點連向所有點權 0），SPFA 計數超過 n 次即有負環。

SPFA 核心代碼

bool spfa() {
    queue q;
    vector cnt(n+1, 0), inq(n+1, 1);
    for (int i = 1; i <= n; ++i) { dis[i] = 0; q.push(i); }  // 全入隊，dis 初始 0

    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto [v, w] : adj[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) {
                    q.push(v); inq[v] = 1;
                    if (++cnt[v] > n) return false;  // 負環
                }
            }
        }
    }
    return true;
}

避坑指南

1. INF 設為 1e18（長整型），防止加權溢出同時保證不參與松弛。
2. 輸出 -1 時必須優先於 -2 判斷（負環含義更強）。
3. 題目保證 x[i+1] ≥ x[i]，故邊 i+1 → i 權 0 方向不可反。

理論延伸

差分約束 ⇔ 最短路 ⇔ 線性規劃對偶。
- 求最值：固定一個變量，跑最短路得最大值，跑最長路得最小值。
- 判斷可行性：加超級源點跑 Bellman-Ford/SPFA 檢測負環。
- 經典應用：任務調度、佈局設計、時間窗約束。