HDU 1384 差分約束系統：最長路解決區間最小覆蓋

問題建模

給定 n 個區間，每區間至少出現 C 個數字。求滿足條件的最小數字總個數。

設 S[i] 為前綴和（0 到 i 選取的數字個數）。約束轉化為：

• 區間 [a,b] 至少 C 個：S[b] - S[a-1] ≥ C → S[a-1] - S[b] ≤ -C（最長路 ≤ 形式）
• 隱含單調性：0 ≤ S[i] - S[i-1] ≤ 1 → S[i-1] - S[i] ≤ 0、S[i] - S[i-1] ≤ 1

求最小總數即求 S[T] - S[S] 最小值，對應最長路問題。用 SPFA 求最長路（邊權可為負）。

AC 代碼片段

#include 
#include 
#include 
#include 
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50010;

int dis[maxn], head[maxn], n, k;
bool vis[maxn];
struct Edge { int to, w, next; } E[maxn*10];

void add_edge(int u, int v, int w) {
    E[k] = {v, w, head[u]}; head[u] = k++;
}

void spfa(int S) {
    queue q;
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push(S); dis[S] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 0;
        for (int i=head[u]; i!=-1; i=E[i].next) {
            int v = E[i].to;
            if (dis[u] + E[i].w > dis[v]) {
                dis[v] = dis[u] + E[i].w;
                if (!vis[v]) { vis[v]=1; q.push(v); }
            }
        }
    }
}

int main() {
    int u, v, c;
    while (scanf("%d", &n) != -1) {
        k = 0; memset(head, -1, sizeof(head));
        int S = inf, T = -inf;
        for (int i=0; i= c
            add_edge(v, u-1, 0);        // 隱含約束 S[u-1] - S[v] <= 0
            S = min(S, u-1); T = max(T, v);
        }
        for (int i=S+1; i<=T; i++) {
            add_edge(i-1, i, 1);        // S[i] - S[i-1] <= 1
            add_edge(i, i-1, 0);        // S[i-1] - S[i] <= 0
        }
        spfa(S);
        printf("%d\n", dis[T]);
    }
    return 0;
}

差分約束系統標準建模：≥ 型約束求最小值 → 最長路；≤ 型求最大值 → 最短路。SPFA 可處理負權邊。