HDU 3572 Task Schedule：網絡流最大流建模解任務調度

HDU 3572 Task Schedule - 最大流建模詳解

問題：M 台機器，N 個任務。任務 i 需佔用 1 台機器 P_i 天，開始時間 ≥ S_i，結束時間 ≤ E_i。任務可中斷、可在不同機器、不同日期分段完成。機器同一時間只能做一個任務。問是否能完成所有任務。

網絡流建模

• 源點 S → 每個任務 i：容量 P_i（需完成的總天數）。
• 任務 i → 每個可用日期 d (S_i ≤ d ≤ E_i)：容量 1（每天最多佔用 1 台機器）。
• 每個日期 d → 匯點 T：容量 M（每天 M 台機器可並行）。

若最大流等於 ΣP_i，則可行；否則不可行。

Dinic 算法實現要點

• 節點數：1 (S) + N (任務) + maxDay (日期) + 1 (T) ≤ 1 + 500 + 500 + 1 = 1002。
• 邊數：S→任務 N 條，任務→日期 Σ(E_i-S_i+1) ≤ 500×500 = 250,000，日期→T maxDay 條。總邊數約 50 萬，雙向邊 100 萬，需充足數組。
• 優化：BFS 分層時若匯點不可達直接返回；DFS 中加入 l[u] = -1 剪枝（當前弧優化）。

參考代碼框架（C++）

struct Edge { int v, w, next; } edge[555000];
int head[2010], level[2010], M, cnt;

void add(int u, int v, int w) { ... } // 雙向邊

bool bfs() { ... } // 分層圖
int dfs(int u, int f) { ... } // 阻塞流

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        // 初始化、讀入、建圖
        // 計算 maxDay = max(E_i)
        // S=0, 任務 1..N, 日期 N+1..N+maxDay, T=N+maxDay+1
        // 加邊
        int flow = 0, sumP = 0;
        while (bfs()) while (int f = dfs(0, INF)) flow += f;
        printf("Case %d: %s\n\n", tc, flow == sumP ? "Yes" : "No");
    }
}

關鍵點總結

1. 任務可分割 → 任務到日期的邊容量為 1，表示每天最多分配 1 個機器時隙給該任務。
2. 日期到匯點容量 M 表示每天 M 台機器並行上限。
3. Dinic 算法配合當前弧優化足以通過。
4. 注意多測試用例之間清空圖、重置變量。