JSOI 2008 Blue Mary 旅行：網絡流分層圖動態增邊求最短天數

問題建模

有向圖，每天只能乘一班飛機。求從 1 到 n 輸送 T 個人最少天數。關鍵：每天每城市只能停留一次 → 拆點按天分層。

分層圖構造

• 第 d 天城市 i → 節點 (d-1)*N + i
• 原邊 (u,v) → 第 d 天 u 連第 d+1 天 v，容量 1
• 每天城市自環：第 d 天 i 連第 d+1 天 i，容量 INF（代表停留）
• 源點 1，匯點 n 的各天節點連超級匯點

動態增邊策略

1. 天數 d 從 1 遞增
2. 添加第 d 天的所有邊（飛機邊 + 停留邊）
3. 在現有流基礎上繼續跑最大流（Dinic）
4. 當流量 ≥ T，輸出當前天數 d

優化關鍵

• 不重建圖，直接在殘量網絡上增廣
• 上界天數 n + T 足夠（最壞每天輸送 1 人）
• 當前流量檢查避免多跑無用輪次

複雜度

節點數 O((n+T)·n)，邊數 O((n+T)·m)。Dinic 實際極快，配合動態增邊單調性，總時間可控。

核心代碼邏輯

for (int day = 1; ; ++day) {
    add_day_edges(day);  // 添加飛機邊+停留邊
    while (bfs()) 
        while (flow = dfs(S, INF)) total += flow;
    if (total >= T) { printf("%d", day); break; }
}