HDU 3592 World Exhibition：差分約束系統與 SPFA 判斷可行性

題目大意

n 個變量 S₁..Sₙ，兩類約束：

• x 條：S_b - S_a ≤ c
• y 條：S_a - S_b ≤ -c (即 S_b - S_a ≥ c)

求 S₁ 到 Sₙ 的最短路（即 Sₙ - S₁ 的最大可能值）。輸出：-1(負環無解)、-2(不可達)、或最短距離。

差分約束建模

每個約束 S_v - S_u ≤ w 轉化為有向邊 u → v，權重 w。求 S₁ 到 Sₙ 最短路等價於求 Sₙ - S₁ 的最大值（因約束為 ≤）。

SPFA 算法實現

#include 
#include 
#include 
#include 
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct Edge { int to, w, next; } e[30020];
int head[MAXN], ecnt;
int dist[MAXN], inq[MAXN], cnt[MAXN];
int n;

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

bool spfa(int s) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    dist[s] = 0;
    queue q;
    q.push(s);
    inq[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        if (++cnt[u] > n) return false;  // 負環檢測
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    return true;
}

int main() {
    int T, x, y, a, b, c;
    scanf("%d", &T);
    while (T--) {
        memset(head, -1, sizeof(head));
        ecnt = 0;
        scanf("%d%d%d", &n, &x, &y);
        while (x--) {
            scanf("%d%d%d", &a, &b, &c);
            addEdge(a, b, c);  // S_b - S_a ≤ c
        }
        while (y--) {
            scanf("%d%d%d", &a, &b, &c);
            addEdge(b, a, -c);  // S_a - S_b ≤ -c
        }
        if (!spfa(1)) printf("-1\n");
        else if (dist[n] != INF) printf("%d\n", dist[n]);
        else printf("-2\n");
    }
    return 0;
}

關鍵點解析

SPFA 優化技巧

• SLF (Small Label First)：新節點距離 < 隊首距離則插隊首
• LLL (Large Label Last)：隊首距離 > 平均距離則移至隊尾
• 標記入隊次數：比標記鬆弛次數更準確檢測負環

複雜度分析

• 邊數：x + y ≤ 20000
• SPFA 平均 O(k·E)，k 為平均鬆弛輪數，通常很小
• 最壞 O(VE) 但隨機圖極難觸發
• 空間 O(V+E)

差分約束經典應用場景

1. 項目調度：任務間最早/最晚開始時間
2. 佈局設計：模塊相對位置約束
3. 網絡路由：延遲約束下的最短路
4. 資源分配：供需平衡不等式系統

總結

HDU 3592 是差分約束 + SPFA 模板題。核心步驟：

1. 不等式轉有向邊
2. SPFA 求單源最短路
3. 負環 → -1，不可達 → -2，可達 → 輸出距離

注意：本題求 Sₙ - S₁ 最大值，對應最短路；若求最小值則對應最長路（需無正環）。