UVa 515 King：差分約束系統 + SPFA 判斷可行性

題目大意

序列 S₁...Sₙ，給 m 條約束：`S[a] + ... + S[a+b] > k` 或 `< k`。判斷是否存在滿足所有約束的整數序列。n ≤ 100, m ≤ 100。

建模：差分約束系統

• 定義前綴和 `X[i] = S₁ + ... + Sᵢ`，`X[0] = 0`。
• 區間和 `S[a..a+b] = X[a+b] - X[a-1]`。
• 約束轉化：
  `gt` (>)：`X[a+b] - X[a-1] ≥ k+1` ⇒ `X[a-1] - X[a+b] ≤ -(k+1)`。
  `lt` (<)：`X[a+b] - X[a-1] ≤ k-1` ⇒ `X[a+b] - X[a-1] ≤ k-1`。
  形式統一為 `X[v] - X[u] ≤ w`，即邊 `u → v` 權 `w`。

求解：SPFA 判負環

• 添加超級源點 `n+1`，向所有點連邊權 0（保證圖連通）。
• 跑 SPFA 求最短路。若存在負環（某點入隊次數 > n+1），則無解。否則有解。

代碼

#include 
#include 
#include 
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

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

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

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

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        int m; scanf("%d", &m);
        memset(head, -1, sizeof(head));
        ecnt = 0;
        for (int i = 0; i <= n; ++i) addEdge(n+1, i, 0); // 超級源點
        for (int i = 0; i < m; ++i) {
            int a, b, k; char op[5];
            scanf("%d%d%s%d", &a, &b, op, &k);
            int u = a-1, v = a+b;
            if (op[0] == 'g') addEdge(v, u, -(k+1)); // gt
            else addEdge(u, v, k-1); // lt
        }
        if (spfa(n)) puts("lamentable kingdom");
        else puts("successful conspiracy");
    }
    return 0;
}

關鍵點

• **前綴和變換** 將區間和約束轉為兩變量差分約束。
• **超級源點** 連接所有點權 0，解決 SPFA 需連通圖的問題。
• **負環判斷**：入隊次數超過節點數即存在負環 ⇒ 無解。
• **輸出映射**：有解 → "lamentable kingdom"，無解 → "successful conspiracy"。

總結

UVa 515 是「差分約束系統 + SPFA」的標準模板題。核心步驟：前綴和建模 → 差分約束圖 → 超級源點 → SPFA 檢測負環。掌握此流程，可解決所有線性不等式組可行性判斷問題。