“最长k可重区间集问题”这名字第一次出现在《网络流24题》里时我就被“最长”两个字骗了以为又是一道区间贪心题。直到看到标准解法是最大费用最大流才意识到这里的“最长”不是指最长区间而是让选出的区间总长度最大同时还要保证数轴上任意一个点被覆盖的次数不超过 k。换句话说给你一批开区间每个区间选一次能获得它的长度作为收益最多允许 k 个区间同时压到同一点求最大收益。如果你正在刷费用流这道题是理解“流即资源、边即事件”的极好素材如果你只会套模板看完这篇之后至少能明白那几条链边和区间边为什么长成那样下次遇到调度类问题也知道该往哪个方向靠。1. 先拆题它为什么不是贪心题1.1 问题到底描述了什么样题面非常短但信息量不小。给你 n 个开区间 (l_i, r_i)每个区间有一个长度 r_i - l_i作为选中它的收益。再给你一个整数 k要求选若干个区间使得实轴上任意一点 x 被选中的区间覆盖的次数不超过 k。求选中的区间总长度最大是多少。这里最关键的两个词是“开区间”和“任意一点”。开区间意味着端点不参与覆盖。比如 (1,3) 和 (3,5) 这两个区间虽然 3 这个数在两个区间里都作为端点但开区间不包含 3所以点 3 被覆盖的次数是 0这两个区间可以同时选。这个细节特别容易错后面我会专门说。“任意一点被覆盖不超过 k”就是“最多有 k 个区间同时覆盖同一个点”的意思。换句话说允许区间重叠但重叠层数不能超过 k。拿一个具体例子有三个区间 (1,3)、(2,4)、(3,5)长度都是 2k2。你可能会想当然地选前两个总长度 4但仔细检查点 2.5 确实被前两个覆盖了 2 次合法点 3 只被 (2,4) 覆盖也合法。可是如果贪心选不相交的区间只能选 (1,3) 和 (3,5)总长度也是 4但这不是最优因为开区间的情况下三个区间可以同时选点 2.5 被两个覆盖点 3.5 被两个覆盖没有任何点超过 2 层总长度是 6。贪心按左端点排序、尽量选不重叠区间的做法在这里直接吃瘪。所以这个问题的难点在于 k 层的重叠限制。k1 时就是经典的最大权不重叠区间选择可以排序后 DP。k1 时DP 状态里需要记录每个坐标点当前的覆盖数坐标一多就完全没法做。这时候网络流出现了。1.2 从“覆盖次数”想到“流量”我的理解方式是把数轴看成一条从左到右的单向道路有 k 辆车同时从最左端出发开往最右端。每个区间相当于一段可选的“接送段”车走完这段能获得收益但一段路最多只能被一辆车走一次。为什么会想到这个类比因为“任意一点最多被 k 个区间覆盖”这句话可以翻译成“任意一点同时在路上行驶的车辆数不超过 k”。总共有 k 辆车那么就算它们全挤在同一个位置车辆数也就是 k天然满足限制。选择区间就是让其中一辆车从 l 开到 r并在这段路程中占用道路不选区间时车沿着链边空驶不产生收益。这样一个“区间选择问题”就变成了“k 条路径从起点到终点的流量分配问题”网络流里的流量单位正好对应一辆车。这个类比并不是我硬凑的它和“区间图染色”有严格的对应关系。任意一组满足覆盖次数不超过 k 的合法区间集合因为区间图的最大团大小不超过 k所以区间一定可以用不超过 k 种颜色染色使得相同颜色的区间两两不重叠。每种颜色对应一辆车同色区间按坐标顺序连起来就是一辆车从起点到终点经过的路线。这就说明合法区间集合确实能对应到 k 条路径。反过来一个流量为 k 的整数可行流可以分解成 k 条从源点到汇点的路径。由于所有边方向都是从左到右每条路径上的区间边互不重叠对应一辆车的行车路线。任意一个点同一辆车的路径最多只有一个区间覆盖它k 辆车合计覆盖次数不超过 k所以网络流方案也一定对应合法区间集合。这一步想通之后整道题的核心就出来了把区间当作边把资源数 k 当作总流量把收益当作费用跑最大费用流。1.3 合法性与最优性的等价证明再严谨一点说我们建立的网络里任意一个满足流量守恒、容量限制的整数流总流量为 k。把它分解成路径每条路径由链边和区间边交替组成。链边只是在相邻关键点之间移动不产生任何区间选择区间边才代表真正选了一个区间。费油是路径上所有区间边费用之和。由于费用只挂在区间边上一个流的费用恰好等于选中的所有区间长度总和。因此任何一个网络流方案 → 一个合法的 k 可重区间选择覆盖次数不超过 k任何一个合法选择 → 可以先按区间图染成 k 色再构造成一个流流量为 k费用为总长度。两边是一一对应且费用相同的所以最大费用流就是最优解。后面所有建图细节都是为了把这个网络精确地建出来。2. 建图把数轴压缩成一条链2.1 坐标离散化端点才是关键实际做题时区间端点的范围可能非常大比如从 -1e9 到 1e9不可能在数轴上每个单位都建一个点。值得庆幸的是覆盖次数发生变化的位置只会出现在区间端点处。在相邻两个端点之间不管覆盖情况怎样它都是恒定不变的因为没有任何区间会在中间开始或结束。所以把所有区间的 l 和 r 都收集起来排序去重得到一个长度为 m 的关键点数组 xs。原来的数轴被压缩成 m 个离散节点相邻节点之间用一条链边连接。每个区间的左端点对应 xs 中的某个下标 u右端点对应某个下标 v区间就变成了从 u 到 v 的一条边。离散化的细节很简单vectorint xs; for (auto [l, r] : interval) { xs.push_back(l); xs.push_back(r); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());之后用一个 lower_bound 函数拿到任意端点对应的节点编号。注意因为区间的左右端点都插进去了所以离散化后 u v 一定成立。2.2 三类边各司其职建图一共只需要三类边第一类源点 S 到第一个关键点容量 k费用 0。这表示同时有 k 个单位流量k 辆车从最左边出发。为什么容量必须是 k因为整个问题的核心限制就是不能超过 k 层流量一多路径分解出来的车辆就超过 k 了。第二类相邻关键点之间的链边容量设成 INF费用 0。比如节点 i 连到 i1。这条边的含义是车辆当前不选择任何区间单纯从上一个关键时刻挪到下一个关键时刻。容量设 INF 是安全的因为从源点总共只放了 k 个流量网络中任意截面上的流量都不会超过 k所以即使链边容量很大实际流量也被源头限制住了。有人喜欢把链边容量设成 k也能过但没必要反而容易让人误解。第三类每个区间对应的边。离散化后左端点节点 u 到右端点节点 v容量 1费用为区间长度。容量 1 表示每个区间最多被选一次费用为长度表示选中这个区间能获得的收益。如果题目改成求最多选多少个区间费用改成 1 就行。最后最后一个关键点连到汇点 T容量 k费用 0表示车辆到达终点完成任务。整个网络是一个非常简单的有向无环图结构源点 → 第一个点 → 第二个点 → … → 最后一个点 → 汇点中间穿插着一条条“跃迁边”表示区间。这种形态我习惯叫“链上搭边”。2.3 容量和费用背后的“为什么”很多初学者会问为什么区间边容量一定是 1反过来想如果容量设成 INF同一个区间可能被多个流量同时选择相当于同一辆车重复跑同一段路显然不合理。容量 1 保证了每个区间最多贡献一次费用。为什么链边可以用 INF因为链边对应“不选区间”的空驶状态它不产生费用即使多个流量同时走同一条链边也没关系它们只是并行前进不会改变覆盖计数。真正需要限制的是区间边和源点流量。为什么要用最大费用流而不是最大流因为我们的目标是收益最大不是选得越多越好。网络流的“流量”只表示资源的数量不直接表示收益收益靠边上费用累积。最大费用流会在所有可行流里找费用最大的那个流量方案正是我们要的答案。还有一个细节如果某个区间长度为 0也就是 lr它的边会形成一个自环。自环在费用流里虽然不一定爆炸但没有任何意义还会让离散化 lower_bound 出现问题。读入时直接跳过 lr 的区间最省事。3. 最大费用流求解与代码3.1 选择求最长路而不是最短路网络流模型建好之后剩下的就是实现。费用流常规套路有两种最小费用最大流和最大费用最大流。这里收益是正的我们希望费用最大所以最直接的想法是每次找一条“总收益最大”的增广路也就是最长路。图里存在反向边而且反向边的费用是负的所以不能用 Dijkstra 直接跑最短路。用 SPFA 求最长路是符合直觉的写法。SPFA 可以处理负权边只要图中没有正环就可以安全运行。这里的网络在最开始是一个 DAG增广过程中虽然会引入反向边但连续最短路算法的正确性保证了中间流都是当前流量下的最优费用流残留网络里不会出现正环所以 SPFA 最长路是安全的。每次找到从 S 到 T 的一条最长路后如果这条路的总费用 0说明再选区间也不可能增加收益了直接停止增广。否则按路径上的最小剩余容量增广把费用累加到答案里。由于区间边容量为 1一次增广的流量通常是 1所以增广次数不会超过 k整体复杂度很低。3.2 增广流程的直觉解释想象一下 SPFA 每轮找出的是当前残留网络上“最能赚钱”的一条从起点到终点的路径。这条路径可能包含反向边反向边对应“之前选的某个区间现在撤销”撤销当前选择再把流量调整到另一条更赚钱的路上去这正是费用流能退流的原因。如果最赚钱的路径收益都是 0 或负数说明再继续增加区间选择已经没有正收益继续跑下去只会做无用功所以直接退出。因为链边费用是 0总有一条纯链边的零收益路径存在因此最长路收益不会小于 0判断dis[T] 0退出是安全的。3.3 参考实现C17下面给出一个完整的可提交代码。这份代码以开区间、长度为收益为默认模型如果需要改成区间个数把区间边的费用参数改成 1 即可。#include bits/stdc.h using namespace std; using ll long long; const int N 1010; const int M 100005; const int INF 1e9; struct Edge { int v, cap, nxt; ll cost; } e[M 1]; int head[N], tot; void init() { memset(head, -1, sizeof(head)); tot 0; } void add_edge(int u, int v, int cap, ll cost) { e[tot] {v, cap, head[u], cost}; head[u] tot; e[tot] {u, 0, head[v], -cost}; head[v] tot; } int n, k; vectorint xs; vectorpairint, int rawSegs; int get_id(int x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin() 1; } ll dis[N]; int pre[N], preedge[N]; bool inq[N]; bool spfa(int s, int t) { for (int i 0; i t; i) dis[i] -INF; memset(inq, 0, sizeof(inq)); memset(pre, -1, sizeof(pre)); queueint q; dis[s] 0; q.push(s); inq[s] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].v; if (e[i].cap 0 dis[v] dis[u] e[i].cost) { dis[v] dis[u] e[i].cost; pre[v] u; preedge[v] i; if (!inq[v]) { q.push(v); inq[v] true; } } } } return dis[t] ! -INF; } ll maxCostFlow(int s, int t) { ll cost 0; while (spfa(s, t)) { if (dis[t] 0) break; int flow INF; for (int v t; v ! s; v pre[v]) { flow min(flow, e[preedge[v]].cap); } for (int v t; v ! s; v pre[v]) { int eg preedge[v]; e[eg].cap - flow; e[eg ^ 1].cap flow; } cost dis[t] * flow; } return cost; } int main() { scanf(%d%d, n, k); for (int i 0; i n; i) { int l, r; scanf(%d%d, l, r); if (l r) continue; rawSegs.push_back({l, r}); xs.push_back(l); xs.push_back(r); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); int m xs.size(); int S 0, T m 1; init(); add_edge(S, 1, k, 0); for (int i 1; i m; i) { add_edge(i, i 1, INF, 0); } add_edge(m, T, k, 0); for (auto seg : rawSegs) { int u get_id(seg.first); int v get_id(seg.second); ll len seg.second - seg.first; add_edge(u, v, 1, len); } printf(%lld\n, maxCostFlow(S, T)); return 0; }代码逻辑并不复杂。建图完成后直接跑maxCostFlow返回的值就是最大总长度。如果题目要求输出的是区间数量版把add_edge(u, v, 1, len)改成add_edge(u, v, 1, 1)就行。代码里有一个需要注意的地方dis数组初始化为-INF而不是 0。因为存在负权反向边如果初始为 0某些负费用边可能错误地被认为是不可达路径。使用-INF可以保证每条源点可达的路径都能被正确更新。4. 实战中容易踩的坑4.1 开区间和闭区间是最大的坑我在第一次做这道题时样例怎么都对换个大样例就开始 WA原因就是我把区间当成闭区间处理了。原题背景里的区间通常是开区间也就是两个区间在端点重合不算覆盖。比如 (1,3) 和 (3,5)端点 3 不参与覆盖所以两个区间可以同时选。如果你按闭区间思维建图默认 3 这个点被两个区间覆盖那么这两个区间就不能同时选答案会偏小。如果题目明确是闭区间怎么改经典做法是把右端点映射成它的“下一个关键点”。比如离散化后区间 [l, r] 变成从 l 到 r 的下标加 1相当于用一个半开区间 [l, r1) 来表示闭区间覆盖。另一种做法是把所有端点坐标都乘 2然后左端点用 2l右端点用 2r1但这种方法写起来容易错我更喜欢右端点加一。无论用哪种都要时刻记住网络流模型里每条边跨越的是“段”不是“点”。建图前先确认题目给的是开区间还是闭区间再决定要不要平移端点这个习惯能帮你省下大量调试时间。4.2 费用流模板细节反向边、SPFA、精度反向边必须写而且费用要是正向边的相反数。add_edge 里第二个 add_edge 的容量为 0、费用为 -cost。少了反向边流量无法退流最终答案一定不是最优。SPFA 判断条件建议用不要用。虽然这道题没有正环但用在个别模板里可能因为重复松弛导致死循环。保持严格小于更稳定。每次 SPFA 前要重置 pre 数组。因为残留网络里的边一直在变化上一次增广路径上的 pre 如果残留可能导致这次回溯路径时跳到错误节点。费用可能超过 int建议用long long。特别是区间数量多、长度大的时候总长度轻松超过 2e9。如果区间的权值不是长度而是读入的任意整数那也要用 long long 存。注意如果权值可能为负最大费用可行流和最大费用最大流的区别就会显现需要仔细斟酌是否允许不选负权区间。一般题目不会出负权开区间长度恒为正放心用。4.3 边界情况与数据范围l r 的区间直接跳过。长度为 0 的区间选了不增加收益放在网络里只会形成自环或退化边没什么意义。重复区间不需要去重。每个区间都是一条独立的容量为 1 的边可以同时选多次只要覆盖层数不超 k。比如 k2有两个完全相同的区间 [1,5]可以都选覆盖 2 层合法收益叠加。源点容量和汇点容量都设为 k。中间链边容量没限制。如果 k 很大但可选的区间边有限增广次数其实由有效区间数量决定不用担心复杂度爆炸。离散化后 m 可能很小。链边 O(m)区间边 O(n)总边数非常少。即使 n 上万SPFA 也扛得住因为增广次数被 k 限制。4.4 一个“调包”技巧数量版和权值版这题最常见的变体是不按区间长度算收益而是问最多能选多少个区间同样满足任意点覆盖不超过 k。这时候不需要改结构把每条区间边的费用从 len 改成 1 即可。如果你做过“最长 k 可重区间集”再遇到“最多 k 个不重叠区间”的版本三分钟内就能改完。另一种变体是线段集问题即给定的是实轴上的线段而不是开区间端点覆盖的判定规则可能不同。这种题可以沿用图模型只需处理端点关系。你会发现网络流的建图能力在于把“覆盖”这个操作抽象成“跨过一段弧”弧的起点和终点只要定义清楚模型就成立。5. 延伸从这道题看网络流的建图思维5.1 和区间贪心的关系当 k1 时最大权不重叠区间可以用 O(n log n) 的贪心或 DP 解决这也是很多算法入门书里的经典例题。但当 k 变成变量后简单的贪心就失效了。费用流模型的价值在于它把 k 藏进了流量上限把区间选择藏进了容量为 1 的边把收益藏进了费用。以后看到“k 条路径”“k 个资源”“同时进行最多 k 个”这类字眼应该条件反射想到能否在时间轴或线性坐标上拉一条容量为 k 的链把活动变成从开始到结束的有向边这种“链上加活动边”的建模是网络流 24 题里反复出现的套路。比如最大权闭合图、最长不下降子序列之类的问题核心都是把原问题的合法方案转化成网络中的一条条路径然后用流量的守恒性质自动约束全局。5.2 拆点与链式建模的区别有些题需要限制的是“点”本身比如每个点最多被经过 k 次这时候常用拆点把每个点 i 拆成 i 入点和 i 出点入点到出点连容量 k 的边原来经过 i 的边改成从 i 的入点连到出点或者从入点到入点。这种模型强制每个点内部有一个容量瓶颈。而本题的链式建模没有拆点直接利用源点总流量 k 来保证任意截面流量不超过 k。为什么能这么做因为流量在链上是守恒的从源点出发的总流量是 k那么任意一个垂直切面上流过的总流量不会超过 k。区间边也是从左到右跨过切面的它和链边共享同一个流量池所以覆盖层数被天然限制。当你不需要给点设置独立容量只需要限制总层数时链式建模比拆点更简洁。理解这两种建模的区别能帮你以后快速判断该用哪种。5.3 以后遇到类似题怎么想我的建议是套用三步第一步识别约束。看到“最多 k 个同时”“任意点覆盖不超过 k”“k 条路径”先想到流量上限 k。第二步定义“段”。把活动或区间看成一条从起始时刻到结束时刻的边收益作为费用。如果活动覆盖的是连续坐标就离散化端点用端点之间的链边相连。第三步跑费用流。费用为正找最长路费用为负取反跑最短路。如果问题要求必须选满 k 个资源就强制满流如果只是可行流就允许在收益为 0 时停止。这套流程看起来简单但真正有用的是第二步里的“段”怎么定义。开区间、闭区间、线段、点权都是各种细节的变化想清楚“边跨过什么”再动手。最后说点自己的感受。“最长 k 可重区间集”我前前后后写了三遍第一遍照着题解背第二遍明白链边是“车”第三遍才懂它其实就是给 k 个资源分配时间线的过程。每次刷费用流遇到新题我都会回来看看这个模型。如果你现在卡在这里我的建议是先不要背模板拿纸笔画一条数轴想象 k 辆车从左边开过去哪个区间让哪辆车载客覆盖次数超过 k 是什么样子画通了代码自然写得顺。就是“画图想车”这个习惯让我后来做“最长 k 可重线段集”的时候十分钟就建好了图。