HDU 3572 Task Schedule：網絡流 Dinic 算法解決任務調度

HDU 3572 Task Schedule：網絡流 Dinic 算法解決任務調度

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

網絡流建模

• 源點 S，匯點 T。
• 時間點節點：1..T_max (T_max = max E_i)。
• S → 每天節點：容量 M（每天 M 台機器）。
• 每天節點 → 任務節點：若天屬於任務區間，容量 1（每天每任務最多佔用 1 台機器）。
• 任務節點 → T：容量 P_i（任務總需天數）。

最大流 = Σ P_i ⇔ 可行調度存在。

Dinic 算法實現

struct Edge { int to, cap, rev; };
vector G[MAXV];
int level[MAXV], iter[MAXV];

void add_edge(int from, int to, int cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size()-1});
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue q; q.push(s); level[s]=0;
    while (!q.empty()) {
        int v=q.front(); q.pop();
        for (auto& e : G[v])
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v]+1;
                q.push(e.to);
            }
    }
}

int dfs(int v, int t, int f) {
    if (v==t) return f;
    for (int& i=iter[v]; i 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow=0, inf=1e9;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f=dfs(s,t,inf)) > 0) flow += f;
    }
}

建圖代碼

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; cs++) {
        int N, M; scanf("%d%d", &N, &M);
        vector P(N+1), S(N+1), E(N+1);
        int Tmax = 0, sumP = 0;
        for (int i=1; i<=N; i++) {
            scanf("%d%d%d", &P[i], &S[i], &E[i]);
            Tmax = max(Tmax, E[i]);
            sumP += P[i];
        }
        // 初始化圖
        int S_node = 0, T_node = Tmax + N + 1;
        for (int i=0; i<=T_node; i++) G[i].clear();
        // S -> 天
        for (int d=1; d<=Tmax; d++) add_edge(S_node, d, M);
        // 天 -> 任務
        for (int i=1; i<=N; i++) {
            int task_node = Tmax + i;
            for (int d=S[i]; d<=E[i]; d++)
                add_edge(d, task_node, 1);
            // 任務 -> T
            add_edge(task_node, T_node, P[i]);
        }
        int flow = max_flow(S_node, T_node);
        printf("Case %d: %s\n\n", cs, flow == sumP ? "Yes" : "No");
    }
}

關鍵點

1. 任務可分割、可跨機器，故「天 → 任務」容量 1 正確建模「每天每任務最多 1 台機器」。
2. 時間範圍 ≤ 500，節點數 ≈ 500 + 500 = 1000，邊數 ≤ 500×500 = 25萬，Dinic 極快。
3. 輸出格式：Case x: Yes/No 後空行。

複雜度

• Dinic：O(E√V) 對於二分圖匹配類結構極快，實際 < 100ms。

此題是「區間調度 + 資源限制」建模為最大流的經典案例，展示了流網絡處理時間資源分配的強大表達力。