P2223 [HNOI2001] 软件开发 题解

2025-08-05

对每一天,建立两个点 $d_i, e_i$。分别表示早上和晚上。建立 $s$ 为超级源点,$t$ 为超级汇点。

  • 每一天需要 $n_i$ 个毛巾。也会产生 $n_i$ 个脏毛巾。所以 $s$ 往 $e_i$ 连容量为 $n_i$,价值为 0 的边。 $d_i$ 往 $t$ 连容量为 $n_i$,价值为 0 的边。
  • 每一天的脏毛巾可以留给下一天,所以 $e_i$ 往 $e_{i+1}$ 连容量为 $+\infty$ 的边。
  • 每一天可以购买毛巾,所以 $s$ 往 $d_i$ 连容量为 $+\infty$ 价值为 $f$ 的边。
  • 每一天可以用第一种方式清洗毛巾,所以 $e_i$ 往 $d_{i+a}$ 连容量为 $+\infty$ 价值为 $f_A$ 的边。
  • 每一天可以用第二种方式清洗毛巾,所以 $e_i$ 往 $d_{i+b}$ 连容量为 $+\infty$ 价值为 $f_B$ 的边。

最后跑最小费用最大流即可。