题解 P1251 【餐巾计划问题】

· · 题解

费用流卡不过去怎么办？

我们可能需要一种 O(n\log^2 n) 的算法。

考虑逐单位流量增广费用流的过程，每增广一单位流量，增加的费用是不减的。

如果要求最小费用可行流，可以二分出增加费用大于 0 的流量，然后求这个流量下的最小费用。

求特定流量下的最小费用，在这个问题中就是用给定数量的餐巾分配给每天使得满足要求的最小费用。

这个问题可以贪心，用并查集优化可以做到 O(n\log n)。

于是总复杂度就是 O(n\log^2 n) 了。