HDU 3572 Task Schedule：最大流 ISAP 解任務調度

問題描述

M 台機器，N 個任務。任務 i 需在 [S_i, E_i] 內處理 P_i 天，可中斷、可換機器。每天每台機器只能做一任務，每任務每天只能佔一機器。問是否存在可行調度。N≤500, M≤200, 時間≤500。

最大流建模

• 源點 S → 任務節點 i，容量 P_i（總需處理天數）。
• 任務 i → 時間節點 t (S_i ≤ t ≤ E_i)，容量 1（每天最多佔 1 機器）。
• 時間節點 t → 匯點 T，容量 M（每天最多 M 台機器）。
• 最大流 = ΣP_i 則可行。

ISAP 算法實現

struct Edge { int to, next, cap, flow; } e[520010];
int head[1010], gap[1010], dis[1010], cur[1010], S[1010];

void addEdge(int u,int v,int c) { ... } // 前向+反向邊

void bfs(int s, int t) { ... } // 反向 BFS 計算距離標號

int maxFlow(int s, int t, int n) {
    bfs(s,t);
    if (dis[s]==-1) return 0;
    memcpy(cur,head,sizeof(head));
    int u=s, top=0, flow=0;
    while (dis[s] < n) {
        // 尋找可推進邊
        // 更新距離標號、gap 優化
        // 增廣並回溯
    }
    return flow;
}

關鍵點

• 節點數：1 (S) + N + 500 (時間) + 1 (T) ≤ 1002。
• 邊數：N + N*500 + 500 ≤ 250k，雙向 500k，數組開足。
• ISAP 比 Dinic 更快，適合稠密分層圖。
• 時間節點編號偏移 N，避免衝突。

總結

HDU 3572 是「任務調度 → 最大流」的經典建模。關鍵在於將「時間」作為中間層節點，容量限制對應資源約束。ISAP 算法配合 Gap 優化、當前弧優化，能高效解決此類大規模二分圖流問題。