HDU 3572 Task Schedule 最大流建模任務調度

問題描述

n 個任務，m 台機器。任務 i 在 [s_i, e_i] 區間內需佔用機器 p_i 天（可分割，但同一天一台機器只能做一個任務）。問是否能安排完成所有任務。

最大流建模

• 源點 S → 任務節點 i，容量 p_i
• 任務 i → 天數節點 d（s_i ≤ d ≤ e_i），容量 1
• 天數節點 d → 匯點 T，容量 m（每天 m 台機器）

最大流 = ∑p_i 則可行。

Dinic 算法實現

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

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

bool bfs(int s, int t) {
    fill(level, level+MAXV, -1);
    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 t, int f) {
    if (u == t) return f;
    int flow = 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 ret = dfs(v, t, min(f, e[i].cap));
            if (ret) {
                e[i].cap -= ret;
                e[i^1].cap += ret;
                return ret;
            }
        }
    }
    return 0;
}

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

節點編號規劃

• 源點：0
• 任務 1..n：1 到 n
• 天數 1..500：n+1 到 n+500（題目時間上限 500）
• 匯點：n+501

複雜度

節點數 ~ n+500，邊數 ~ n×500。Dinic 在二分圖類問題上接近 O(E√V)，完全可行。