POJ 1698 Alice's Chance：最大流建模解決電影拍攝調度問題

某導演要在 K 周內拍完 N 部電影，每部電影每周有固定可拍攝天數，且必須在第 Ki 周前殺青。問是否存在可行調度。本質是二分圖最大流建模：電影 → 可用天 → 匯點，滿流即可行。

建模邏輯

1. 源點 S 連向每部電影節點 i，容量 = 該電影所需拍攝天數 need[i]。
2. 電影 i 連向其可拍攝的具體日期節點 d（第 w 周第 d 天），容量 = 1（每天只能拍一部）。
3. 日期節點 連向匯點 T，容量 = 1（每天只能用於一部電影）。
4. 日期總數 = max_week * 7，節點總數 ≤ 400，邊數 ≤ 10000，Dinic 瞬時解出。

關鍵建模細節

• 輸入給出每部電影：a[i][1..7]（周一至周日是否可拍，1/0）、need[i]（所需天數）、deadline[i]（截止周）。
• 僅在第 1 周至 deadline[i] 週內的可拍天建立邊。
• 最大週數 MaxWeek = max(deadline[i])，日期節點編碼：n + (week-1)*7 + day。

Dinic 核心代碼（同 POJ 1273）

// 見上篇，此處略。關鍵點：
// 1. 反向邊 cap 初始為 0，構建時 addEdge(u,v,cap) 自動添加反向邊
// 2. BFS 分層 + DFS 當前弧優化
// 3. 最大流值 = 所有 need[i] 之和 即為可行

判斷邏輯

int total_need = 0;
for (i=1..n) total_need += need[i];
int flow = dinic(S, T);
if (flow == total_need) puts("Yes");
else puts("No");

複雜度

• 節點 ≤ 100 (電影) + 50*7 (日期) + 2 ≈ 452
• 邊 ≤ 100*50*7 ≈ 35000
• Dinic O(E√V) 極快，毫秒級。

總結

本題是最大流建模經典範例：將調度問題轉化為二分圖流網絡，「資源（天）」作為中間層節點，容量限制自然編碼約束。關鍵能力：

1. 識別「供給方（電影需求）」與「需求方（時間資源）」
2. 正確設置節點容量（源→電影=需天數，電影→天=1，天→匯=1）
3. 處理截止時間約束（只連截止周前的天）

掌握此建模範式，可解決大量資源分配、任務調度、匹配決策問題。