网络流24题 加强版 P4480 [BJWC2018] 餐巾计划问题

https://www.luogu.com.cn/problem/P1251 为弱化版。

我们发现建图非常简单。拆个点，随便模拟题意连即可。

但是！网络流太笨了。加强版 P4480 就必须要贪心了。

于是我一年前用 SSP 水过了加强版 P4480。

以下变量定义按照 https://www.luogu.com.cn/problem/P1251 来，因为他区分了快洗慢洗。

来讲一下贪心。假设说已知买的餐巾数量。

那么我们可以线性贪心。

设d p i dp_idpi​为到i ii还剩多少餐巾没洗。

贪心到i ii，则有：

• r i ≤ d p i − n r_i \le dp_{i-n}ri​