POJ 1364 King：差分約束系統求解詳解

問題背景與理解

這是一道經典的差分約束問題。故事講述一位能力有限的國王只能對整數序列的連續子序列求和並與給定整數比較大小。給定一系列形如 as + as+1 + ... + as+n < k 或 > k 的約束條件，判斷是否存在一個整數序列滿足所有條件。

核心建模：前綴和與差分約束

設前綴和 Si = a1 + a2 + ... + ai，其中 S0 = 0。則子序列和可表示為 Ss+n - Ss-1。

根據運算符轉換為標準差分約束形式 xj - xi ≤ c：

• gt (大於)：Ss+n - Ss-1 > k → Ss-1 - Ss+n ≤ -k-1
• lt (小於)：Ss+n - Ss-1 < k → Ss+n - Ss-1 ≤ k-1

圖論建模與 Bellman-Ford 判負環

將每個前綴和 Si 視為圖中的節點，每個約束轉化為一條有向邊：

• gt 條件：從 s+n 向 s-1 連邊，權重 -k-1
• lt 條件：從 s-1 向 s+n 連邊，權重 k-1

若圖中存在負環，則約束系統無解，輸出 successful conspiracy；否則輸出 lamentable kingdom。

關鍵代碼實現

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
struct Edge { int u, v, w; } edges[MAXN];
int dist[MAXN];
int n, m;

bool bellman_ford() {
    memset(dist, 0, sizeof(dist));
    // 執行 n 輪鬆弛
    for (int i = 0; i < n; ++i) {
        bool updated = false;
        for (int j = 0; j < m; ++j) {
            if (dist[edges[j].v] > dist[edges[j].u] + edges[j].w) {
                dist[edges[j].v] = dist[edges[j].u] + edges[j].w;
                updated = true;
            }
        }
        if (!updated) return false; // 無負環
    }
    // 第 n+1 輪若仍能鬆弛，說明有負環
    for (int j = 0; j < m; ++j) {
        if (dist[edges[j].v] > dist[edges[j].u] + edges[j].w)
            return true;
    }
    return false;
}

int main() {
    while (cin >> n && n) {
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int s, ni, k; string op;
            cin >> s >> ni >> op >> k;
            int u = s + ni, v = s - 1;
            if (op == "gt") {
                edges[i] = {u, v, -k - 1};
            } else { // lt
                edges[i] = {v, u, k - 1};
            }
        }
        cout << (bellman_ford() ? "successful conspiracy" : "lamentable kingdom") << endl;
    }
    return 0;
}

複雜度分析與注意事項

• 時間複雜度：O(n·m)，n ≤ 100，m ≤ 100，完全可接受
• 初始化 dist 為 0 而非 INF，因為要檢測任意可達的負環
• 注意輸入中的 0 終止塊不需處理