餐巾计划问题
先拆点,将每天拆成两个点,一个表示用完的旧餐巾①,一个表示需要的新餐巾②。
考虑几种边:
- 购买边,从起点往②点连 \(\inf,p\)。
- 快洗边,从前 \(m\) 天往②点连 \(\inf,p\)。
- 慢洗边,从前 \(n\) 天往②点连 \(\inf,f\)。
- 容量限制边
- 从②点往终点连 \(r_i,0\) 的边。(表示只接受 \(r_i\) 条)
- 从起点往①连 \(r_i,0\) 的边。(表示每天恰好用完 \(r_i\) 条)
发现最大流对应恰好用完的情况,跑最小费用最大流即可。