問題描述

N 個任務（N≤500），M 台機器（M≤200）。任務 i：需處理 P_i 天，可在 [S_i, E_i] 區間內靈活安排，可中斷、可換機器。每天每機器只能處理一任務。判斷是否存在可行調度。

最大流建模

• 源點 S 連向各任務節點，容量 P_i（需處理天數）。
• 任務 i 連向其可用時間點 t ∈ [S_i, E_i]，容量 1（每天最多佔用 1 單位處理量）。
• 每個時間點 t 連向匯點 T，容量 M（M 台機器並行）。
• 最大流 = ΣP_i ⇔ 可行調度存在。

關鍵優化：時間點壓縮

時間上限 500，直接展開每一天節點可行（節點數 ≈ 500+500+2 ≈ 1000，邊數 ≈ N×500 + 500 ≈ 25萬），Dinic 極快。無需壓縮。

Dinic 實現

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXV = 2000;
const int MAXE = 500000;
const int INF = 1e9;

struct Edge { int to, cap, next; } e[MAXE];
int head[MAXV], ecnt, level[MAXV], cur[MAXV];
int S, T;

void add_edge(int u, int v, int cap) {
    e[ecnt] = {v, cap, head[u]}; head[u] = ecnt++;
    e[ecnt] = {u, 0, head[v]}; head[v] = ecnt++;
}

bool bfs() {
    memset(level, -1, sizeof(level));
    queue q; q.push(S); level[S]=0;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].to;
            if (e[i].cap>0 && level[v]==-1) {
                level[v]=level[u]+1; q.push(v);
            }
        }
    }
    return level[T]!=-1;
}

int dfs(int u, int flow) {
    if (u==T) return flow;
    int used=0;
    for (int &i=cur[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if (e[i].cap>0 && level[v]==level[u]+1) {
            int f=dfs(v, min(flow-used, e[i].cap));
            if (f>0) {
                e[i].cap-=f; e[i^1].cap+=f;
                used+=f;
                if (used==flow) break;
            }
        }
    }
    if (!used) level[u]=-1; // 關鍵剪枝：無增廣路標記死節點
    return used;
}

int dinic() {
    int flow=0;
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        flow += dfs(S, INF);
    }
    return flow;
}

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        int N, M; scanf("%d%d", &N, &M);
        memset(head, -1, sizeof(head)); ecnt=0;
        S=0; int sumP=0, maxT=0;
        for (int i=1;i<=N;++i) {
            int P,S,E; scanf("%d%d%d", &P,&S,&E);
            sumP += P; maxT = max(maxT, E);
            add_edge(S, i, P);
            for (int t=S; t<=E; ++t)
                add_edge(i, N+t, 1);
        }
        T = N + maxT + 1;
        for (int t=1; t<=maxT; ++t)
            add_edge(N+t, T, M);
        
        int flow = dinic();
        printf("Case %d: %s\n\n", cs, flow==sumP ? "Yes" : "No");
    }
    return 0;
}

關鍵細節

1. 節點編號：任務 1..N，時間點 N+1..N+maxT，源 0，匯 N+maxT+1。
2. 邊容量：任務→時間點 容量 1 保證「每天每任務最多 1 單位」；時間點→匯 容量 M 保證「每天總處理量 ≤ M 台機器」。
3. Dinic 剪枝：if(!used) level[u]=-1 加速後續 BFS，否則大圖易 TLE。
4. 多測試用例：每案例重置 head, ecnt, S, T。

複雜度

• 節點 ≤ 1000，邊 ≤ 250000，Dinic O(E√V) 極快，< 0.5s。

總結

HDU 3572 是「任務調度可行性 → 最大流」的經典建模。核心洞察：

1. 任務處理量 → 源邊容量。
2. 時間資源單位化 → 中間層節點，容量 1 限制佔用。
3. 機器並行度 → 匯邊容量 M。
4. 最大流滿足總需求 ⇔ 可行調度存在。

此「資源分配 → 流網絡」模板適用於所有「可分割任務、時間窗口、有限並行資源」的調度可行性判斷問題。