BZOJ 1221 HNOI 2001 軟件開發：最小費用最大流解餐巾問題

問題建模

每天需 r_i 條毛巾。新買花費 c，快洗 d₁ 天花費 f₁，慢洗 d₂ 天花費 f₂。毛巾可重複使用。求滿足所有天數需求的最小總花費。

網絡流構圖

• 源點 S，匯點 T
• 每天 i 拆為兩點：in_i (2i)、out_i (2i+1)
• S → in_i：容量 r_i，費用 0（當天需求）
• out_i → T：容量 r_i，費用 0（當天歸還）
• S → out_i：容量 INF，費用 c（買新毛巾直接用）
• out_i → in_i+d：容量 INF，費用 f（送洗 d 天后可用）
• out_i → in_i+1：容量 INF，費用 0（毛巾留到第二天不用洗）

最小費用最大流（SPFA + EK）

struct MCMF {
    struct Edge { int to, cap, cost, rev; };
    vector<vector minCostMaxFlow(int s, int t) {
        int flow = 0, cost = 0;
        vector dist, pv, pe;
        while (true) {
            dist.assign(g.size(), INF); pv.assign(g.size(), -1); pe.assign(g.size(), -1);
            dist[s] = 0;
            queue q; q.push(s);
            vector inq(g.size()); inq[s] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop(); inq[u] = false;
                for (int i=0; i dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u; pe[e.to] = i;
                        if (!inq[e.to]) { inq[e.to] = true; q.push(e.to); }
                    }
                }
            }
            if (dist[t] == INF) break;
            int f = INF;
            for (int v=t; v!=s; v=pv[v]) f = min(f, g[pv[v]][pe[v]].cap);
            for (int v=t; v!=s; v=pv[v]) {
                Edge &e = g[pv[v]][pe[v]];
                e.cap -= f; g[v][e.rev].cap += f;
            }
            flow += f; cost += f * dist[t];
        }
        return {flow, cost};
    }
};

完整求解流程

1. 讀入天數、洗滌天數/費用、購買費用
2. 構建上述網絡（節點數 2×天數+2）
3. 跑 MCMF，輸出總費用

關鍵點

1. 拆點技巧：in 代表「需要毛巾」，out 代表「擁有毛巾」
2. 留存邊 out_i→in_i+1 費用 0，體現毛巾可直接留用
3. SPFA 找最短增廣路，適用於負權邊（此處無負權但通用）
4. 數據範圍小（天數 ≤ 100），EK 算法完全足夠

此題是「最小費用流建模」的教科書級案例，將資源重複使用、延遲可用、多種獲取途徑統一建模為網絡流。