自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:25:32，当前版本为作者最后更新于2021-06-16 16:07:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

区间选择模型：

给定 $[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$，就没有下界了。