[NEERC2016] Delight for a Cat 题解

· · 题解

这里转载一下我博客中的一个片段，因为我发现本题的题解基本都是从线性规划的角度进行考虑的，这种方法技巧性极强，且需要一定的数学观察，不适合像我这种无脑选手，所以这里引出一种适用于这类题目的易于理解的费用流模型。

区间选择模型：

给定 [1,m] 中的 n 个区间 [l_i,r_i]，每个区间选择一次的代价为 w_i，最多可以选 c_i 次，要求使得任意点 j 被覆盖次数在 [a_j,b_j] 间，求最小/最大代价。

将 1 到 m+1 连成一条链，尝试用 i\to i+1 边的流量刻画 i 被覆盖的次数。

对于一个区间，我们建立从 l_i 到 r_i+1 的一条边，称为区间边，如果区间边上流过一条流，就表示选择一次这个区间。

源流向 1，m+1 流向汇，首先设确定总流量为 X，那么没有流经 i\to i+1 这条边的流量就是选择了跨过 i 的区间，所以 i\to i+1 的流量为 X-f_i 就表示 i 被覆盖了 f_i 次。

由此，如果我们要限定一个点被覆盖次数在一个区间中，只需要设定 i\to i+1 的流量上下界为 [X-b_i,X-a_i]，然后将区间边费用设为区间代价，容量设为可选次数，最小/最大费用上下界最大流即为答案。

这里 X 可以选取任意一个充分大的数（不小于最大的 b_i）。

例题 31：[网络流 24 题] 最长 k 可重区间集问题

从给定的 m 个开区间中选择尽量多的区间，使得每个位置被不超过 k 个区间覆盖，且区间长度和最大。

模型中的 w_i=1,\ c_i=1,\ a_j=0,\ b_j=k，套用即可。

注意由于所有 b_j 相等，所以令 X=b_j，就没有下界了，可以普通费用流。

例题 32：[NEERC 2016] Delight for a Cat

在 n 小时中的每个小时，猫可以选择吃饭或睡觉，每个小时吃饭或睡觉都有一个愉悦度，但要求任意连续 k 小时中至少有 m_e 小时吃饭，至少 m_s 小时睡觉，问最大总愉悦度。

首先做个小转化：强制每个小时都睡觉，然后可以选择一些小时改成吃饭，连续 k 个小时中吃饭的数量要在 [m_e,k-m_s] 之中。

再做个转换，将”第 i 小时改吃饭“看成一个区间 [i,i+k)，那么上面的条件就等价于对于所有 i\ge k 的点有 i 被这些区间覆盖的次数在 [m_e,k-m_s] 之中。

模型中的 c_i=1,\ a_j=m_e,\ b_j=k-m_s（对于 i\ge k 的 i\to i+1 边），套用即可。

所有 b_j 相等，所以令 X=b_j，就没有下界了。

例题 33：[NOI 2008] 志愿者招募

有 m 个可选操作，每个操作为将 s_i 到 t_i 中每个位置加 1，代价为 c_i，每个操作可以做无限次，要求最后位置 i 上的数不小于 a_i，问最小代价。

模型中的 w_i 是题中的 c_i，模型中的 c_i=+\infty,\ b_j=+\infty，套用即可。

所有 b_j 相等，所以令 X=b_j，就没有下界了。