问题分析

餐厅每天：

• 早上需要提供 $r_i$ 块干净餐巾
• 晚上会获得 $r_i$ 块脏餐巾

餐巾的来源：

1. 购买新餐巾：单价 $P$，当天可用
2. 快洗：$M$ 天后可用，单价 $F$
3. 慢洗：$N$ 天后可用，单价 $S$（$S < F$）
4. 延期送洗：把脏餐巾留到以后送洗

目标：安排 $n$ 天的餐巾使用，最小化总成本。

网络流建模

这是一个最小费用最大流问题。

关键思路：拆点

把每天拆成两个节点：

• 早上节点 $day_i$：需要干净餐巾
• 晚上节点 $night_i$：产生脏餐巾

建图方法

1. 源点 $S$：

   • 连接每个 $day_i$，容量 = $r_i$，费用 = $0$
     → 表示每天必须满足的需求量

2. 购买新餐巾：

   • 从超级源点 $SS$ 向每个 $day_i$ 连边，容量 = $+\infty$，费用 = $P$ → 可以任意购买新餐巾

3. 快洗服务：

   • 从 $night_i$ 向 $day_{i+M}$ 连边（如果 $i+M \leq n$），容量 = $+\infty$，费用 = $F$ → 第 $i$ 天晚上的脏餐巾，快洗后第 $i+M$ 天早上可用

4. 慢洗服务：

   • 从 $night_i$ 向 $day_{i+N}$ 连边（如果 $i+N \leq n$），容量 = $+\infty$，费用 = $S$
     → 第 $i$ 天晚上的脏餐巾，慢洗后第 $i+N$ 天早上可用

5. 延期送洗：

   • 从 $night_i$ 向 $night_{i+1}$ 连边（如果 $i+1 \leq n$），容量 = $+\infty$，费用 = $0$ → 把脏餐巾留到明天再决定如何处理

6. 汇点 $T$：

   • 每个 $night_i$ 连接 $T$，容量 = $r_i$，费用 = $0$ → 确保每天产生的脏餐巾都被正确处理

流量平衡

• 总需求：$\sum_{i=1}^n r_i$
• $SS$ 提供新餐巾，$S$ 提供"虚拟需求"
• 最终 $SS$ 到 $T$ 的最小费用最大流就是最优解

实际上更简单的建模：

• 源点 $SS$ 连每个 $day_i$，容量 = $+\infty$，费用 = $P$（买新）
• $day_i$ 连汇点 $T$，容量 = $r_i$，费用 = $0$（满足需求）
• $night_i$ 连 $day_{i+M}$，容量 = $+\infty$，费用 = $F$（快洗）
• $night_i$ 连 $day_{i+N}$，容量 = $+\infty$，费用 = $S$（慢洗）
• $night_i$ 连 $night_{i+1}$，容量 = $+\infty$，费用 = $0$（延期）
• 源点 $SS$ 连每个 $night_i$，容量 = $r_i$，费用 = $0$（产生脏餐巾）

样例验证

输入：

3 10 2 3 3 2
5
6
7

参数：

• $n=3, P=10, M=2, F=3, N=3, S=2$
• 需求：$r_1=5, r_2=6, r_3=7$

建图后跑最小费用流：

• 总需求 = $5+6+7=18$
• 最优方案（一种可能）：
  • 第1天：买5块新餐巾（费用50）
  • 第2天：买6块新餐巾（费用60）
  • 第3天：买5块新餐巾（费用50），用第1天的脏餐巾快洗2块（费用6）
  • 总费用 = $50+60+50+6=145$

输出：145

算法步骤

1. 读入 $n, P, M, F, N, S$ 和每天需求 $r_i$
2. 构建网络流图：
   • 节点：$SS$（源）, $day_1..day_n$, $night_1..night_n$, $T$（汇）
   • 边：
     • $SS$ → $day_i$：容量∞，费用$P$
     • $day_i$ → $T$：容量$r_i$，费用$0$
     • $SS$ → $night_i$：容量$r_i$，费用$0$
     • $night_i$ → $day_{i+M}$（若存在）：容量∞，费用$F$
     • $night_i$ → $day_{i+N}$（若存在）：容量∞，费用$S$
     • $night_i$ → $night_{i+1}$（若存在）：容量∞，费用$0$
3. 跑 $SS$ 到 $T$ 的最小费用最大流
4. 输出总费用

复杂度分析

• 节点数：$2n+2 \leq 2002$
• 边数：$O(n)$
• 使用 SSP 或 Primal-Dual 算法：$O(f \cdot E)$ 或 $O(f \cdot V \log V)$
• 在 $n \leq 1000$ 时完全可行

总结

这道题通过拆点区分每天的"干净餐巾需求"和"脏餐巾产生"，用容量限制需求，用费用边表示各种决策的成本，将复杂的餐巾调度问题转化为标准的最小费用流问题，是费用流的经典应用。