BZOJ 2668 [CQOI2012] 交換棋子：最小費用最大流建模

問題描述

N×M 網格，每格有移動次數上限。可交換相鄰（8 方向）兩格棋子。給定初始/目標黑棋分布，求最少步數使所有黑棋到達目標位置。

網絡流建模

1. 每格拆為入點 in 和出點 out，連邊 in→out，容量 (limit + is_in + is_out)/2，費用 2。
2. 相鄰格 out→in 連邊，容量 INF，費用 0。
3. 源點 S 向初始黑棋格 in 連邊，容量 1，費用 -1。
4. 目標黑棋格 out 向匯點 T 連邊，容量 1，費用 -1。
5. 跑最小費用最大流，總費用 / 2 即答案。費用 -1 抵消了起點/終點的額外計數。

關鍵代碼（SPFA + EK）

struct MinCostMaxFlow {
    // ... 加邊、SPFA、EdmondsKarp 實現
    int EdmondsKarp() {
        int cost = 0, flow = 0;
        while (SPFA()) {
            int f = INF;
            for (int i = T; i != S; i = from[i]) f = min(f, flow[p[i]]);
            for (int i = T; i != S; i = from[i]) {
                flow[p[i]] -= f; flow[p[i]^1] += f;
            }
            cost += f * f[T]; flow += f;
        }
        return flow == blacks ? (cost >> 1) : -1;
    }
};

注意事項

• 初始/目標黑棋數必須相等，否則直接 -1。
• 格子移動限制 0 表示不可通過，拆點時容量為 0。
• 費用設為 2 和 -1 是為了讓每條實際移動路徑的費用貢獻為 1（來回各算一次，最後除 2）。
• 節點數 ≤ 100×100×2 + 2，邊數 ≈ 8×節點數，SPFA 足夠快。