POJ 1698 Alice's Chance 最大流模板題 (Dinic 算法)

問題建模

有 N 個電影項目，每項需連續工作 D 天。W 周內每周 7 天，給出每周可工作的日期。問能否安排滿足所有項目天數。構建流網絡：

• 超級源點 S 連向每個項目節點，容量 = D。
• 項目節點連向其可工作的具體日期節點 (周數×7+星期)，容量 = 1。
• 每個日期節點連向超級匯點 T，容量 = 1（每天只能安排一項工作）。
• 若最大流 = 所有 D 之和，輸出 Yes，否則 No。

Dinic 算法核心結構

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

void addEdge(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(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 && 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;
    for (int &i = cur[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (e[i].cap && 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, f;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        while ((f = dfs(s, t, INF))) flow += f;
    }
    return flow;
}

節點編號技巧

日期節點編號：50 + weekday + week*10 (week 從 0 開始)，確保唯一。項目節點 1..N，源點 0，匯點 1001。

複雜度

節點 ≤ 1010，邊 ≤ N×7×W + N + 7W ≈ 10⁵。Dinic O(E√V) 極快。