P1251 餐巾计划问题

同一天的餐巾有使用前与使用后两种状态

问题

P1251 餐巾计划问题
餐厅连续 $N$ 天每天需要 $r_i$ 块干净餐巾。可购买新餐巾，也可把脏餐巾快洗或慢洗，洗好后分别在若干天后重新可用；脏餐巾还可以暂存。求满足全部每日需求的最小花费。

数据规模：$1\le N\le2\times10^3$，$1\le r_i\le10^7$，购买和洗涤单价不超过 $10^4$。

本题可以使用费用流来处理，但难点在于如何把时间这个维度放入到网络中。

最自然的第一反应可能是：第 $i$ 天建立一个节点，再从这一天向未来连接洗涤边。

但这样会出现一个问题：购买的新餐巾也是流入第 $i$ 天节点的资源，于是它可以还没有被使用，就直接沿洗涤边流向未来，相当于把一块干净新餐巾直接送去清洗。

状态

由此我们发现问题在于：同一天的餐巾在“使用之前”和“使用之后”已经是两种不同状态。

既然是两种状态，那就直接拆分：对于每一天 $i$，分别建立：

• clean[i]：第 $i$ 天可以用于满足需求的干净餐巾；
• dirty[i]：第 $i$ 天使用结束后，可以留给未来处理的脏餐巾。

注：这里拆点不是为了限制节点容量，而是显式区分同一时刻的不同状态。

转移

• 第 $i$ 天需要 $r_i$ 单位干净餐巾；
• 第 $i$ 天使用结束后，最多产生 $r_i$ 单位可回收的脏餐巾；
• 干净餐巾的需求，可以由购买或者过去的脏餐巾清洗后满足。

于是 clean[i] 负责记录当天的干净需求入口，dirty[i] 负责记录当天之后的脏资源供给。

笔记

这里需要注意，这张网络不是在追踪“同一块餐巾”的完整物理轨迹，因此不存在必须连接的 clean[i] -> dirty[i]。

clean[i] 表示当天需要被满足的干净资源需求，而 dirty[i] 表示当天使用后系统新获得的可回收脏资源配额。

两者都由当天固定使用量 $r_i$ 决定，但不要求由同一单位流依次经过。

1. 每日干净餐巾需求：连接 clean[i] -> T，容量为 $r_{i}$，费用为 $0$：表示第 $i$ 天最多需要接收 $r_i$ 单位干净餐巾。

2. 购买新餐巾：连接 S -> clean[i]，容量为 $inf$，费用为 $p$，一单位流经过这条边，就表示第 $i$ 天购买一块新的干净餐巾，并支付购买费用 $p$。

3. 当天产生的脏餐巾：连接 S -> dirty[i]，容量为 $r_{i}$，费用为 $0$，第 $i$ 天一共只使用 $r_i$ 块餐巾，因此这一天结束以后，也最多只有 $r_i$ 块脏餐巾能够被回收。

4. 保存脏餐巾：如果今天产生的脏餐巾暂时不想清洗，可以连接：dirty[i] -> dirty[i+1]，容量为 inf，费用为 $0$：这表示一块脏餐巾可以继续保存一天，之后再决定是否送洗。

5. 快洗：如果快洗需要 $m$ 天，费用为 $f$，则连接：dirty[i] -> clean[i+m]，容量为 inf，费用为 $f$。

6. 慢洗：如果慢洗需要 $n$ 天，费用为 $s$，则连接：dirty[i] -> clean[i+n]容量为 inf，费用为 $s$。

一单位流经过这样的边，表示使用一块过去产生的脏餐巾，通过对应洗涤方式，在未来某一天转化成一单位可以满足需求的干净餐巾。

所以这张费用流网络真正优化的，其实是：每一天的干净餐巾需求，到底是由 “当天购买”，还是由 “过去某一天产生的脏餐巾经过某种洗涤” 来满足。

但还有一个问题，为什么不保存干净的餐巾呢？

假设某块餐巾准备在第 $j$ 天使用，而它原本可以在更早的第 $k$ 天洗好。那么完全可以让它先沿 dirty 链多保存若干天，推迟送洗，使它恰好在需要的时候洗好。

洗涤没有容量限制，也不存在“越早洗越便宜”的奖励，因此总能找到一个同样优秀的方案，使回收餐巾不必提前进入干净状态。

购买也是一样：如果第 $j$ 天才需要一块新餐巾，就可以直接在第 $j$ 天购买，没有提前购买再保存的必要。所以只保留脏餐巾的时间转移已经足够了。

▶

AC 代码

namespace MCMF { /* 模板代码略 */ }
using namespace MCMF;

ll r[maxn];

void solve( ) {
    int N = read( );

    vector<int> clean( N + 1 );
    vector<int> dirty( N + 1 );

    int tot = 0;
    for( int i = 1; i <= N; ++ i ) {
        dirty[i] = ++ tot;
        clean[i] = ++ tot;
    }
    int S = ++ tot, T = ++ tot;

    for( int i = 1; i <= N; ++ i ) {
        r[i] = read( );
    }

    ll p = read( );
    ll m = read( ), f = read( );
    ll n = read( ), s = read( );

    init( tot );
    for( int i = 1; i <= N; ++ i ) {
        // 当天使用结束后最多产生 r[i] 块脏餐巾
        add_edge( S, dirty[i], r[i], 0 );
        // 当天可以购买新的干净餐巾
        add_edge( S, clean[i], inf, p );
        // 当天需要 r[i] 块干净餐巾
        add_edge( clean[i], T, r[i], 0 );
    }

    for( int i = 1; i <= N; ++ i ) {
        if( i + 1 <= N ) { // 脏餐巾继续保存
            add_edge( dirty[i], dirty[i + 1], inf, 0 );
        }
        if( i + m <= N ) { // 快洗
            add_edge( dirty[i], clean[i + m], inf, f );
        }
        if( i + n <= N ) { // 慢洗
            add_edge( dirty[i], clean[i + n], inf, s );
        }
    }

    auto [flow, mincost] = mincost_maxflow( S, T, tot );
    cout << mincost << "\n";
}