POJ 3169 Layout (差分約束 + Bellman-Ford)

題目重述

同 ID 208547，N 頭牛排成行，ML 條最大距離約束，MD 條最小距離約束。求牛 1 到牛 N 最大可能距離。

差分約束建模

• x_B - x_A ≤ D（最大距離） → 邊 A → B (D)
• x_A - x_B ≤ -D（最小距離） → 邊 B → A (-D)
• 順序約束 x_{i+1} ≥ x_i → x_i - x_{i+1} ≤ 0 → 邊 i+1 → i (0)

Bellman-Ford 求最短路

int Bellman(int s, int t) {
    fill(dis, dis+n+1, INF); dis[s] = 0;
    for (int i=1; i<=n; i++) {
        bool flag = false;
        for (int j=0; j dis[edge[j].u] + edge[j].w) {
                dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
                flag = true;
            }
        }
        if (!flag) break;
    }
    // 負環檢測
    for (int j=0; j dis[edge[j].u] + edge[j].w) return -1;
    return dis[t] == INF ? -2 : dis[t];
}

以 1 為源點，dis[N] 即最大距離。負環返回 -1，不可達返回 -2。