ZOJ 3229：有源匯上下界最大流標準模板（Dinic）

題目大意

屌絲給 m 個女神拍照，計劃 n 天。每天最多拍 C 個女神，每天照片數 ≤ D。每個女神 i 每天拍照數 ∈ [L_i, R_i]。每個女神 n 天總照片數 ≤ G_i。求最大總照片數及每天對每女神拍照數；無解輸出 -1。

網絡流建模

• 源點 S，匯點 T。
• S → 第i天：容量 [0, D]。
• 第i天 → 女神j：容量 [L_ij, R_ij]。
• 女神j → T：容量 [0, G_j]（題目說「不超過 G_i」，下界 0）。

但標準最大流無下界。需轉化為有上下界可行流問題。

有上下界可行流轉化步驟

1. 對每條邊 u→v 下界 low、上界 up，設容量 up - low。
2. 維護點需求 du[v] += low, du[u] -= low。
3. 加超級源 SS、超級匯 TT：du[i] > 0 連 SS→i 容量 du[i]；du[i] < 0 連 i→TT 容量 -du[i]。
4. 加邊 T → S 容量 INF（無下界），形成循環流網絡。
5. 跑 SS → TT 最大流，若流量 = 所有 du>0 之和，則存在可行流。

求最大流（在可行流基礎上）

刪除 SS, TT 及相關邊，保留殘量網絡。在原圖 S → T 上再跑一次最大流，即為在滿足下界條件下的最大流值。

關鍵代碼結構

 0) { addEdge(SS, i, du[i]); sum_du += du[i]; }
        else if (du[i] < 0) addEdge(i, TT, -du[i]);
        
        if (dinic(SS, TT) == sum_du) {
            // 存在可行流
            // 清除 SS,TT 相關邊（head[SS]=head[TT]=-1）
            printf("%d\n", dinic(S, T)); // 最大流
            // 輸出每條原邊流量 = flow + low
        } else puts("-1");
    }
}

關鍵細節

• 邊結構需記錄 low 以便輸出實際流量 flow + low。
• addEdgeWithBounds 同時更新 du 數組。
• 第一次 Dinic 跑 SS→TT 判斷可行性；第二次跑 S→T 求最大流（利用殘量網絡）。
• 輸出順序需與輸入邊順序一致，建議記錄每條業務邊在邊數組中的索引。

複雜度

Dinic O(E√V) 或 O(V²E)，此處 V ≤ n+m+4 ≤ 200，E ≤ n·m + n + m ≤ 40000，極快。