“最长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)，长度都是 2，k=2。你可能会想当然地选前两个，总长度 4；但仔细检查，点 2.5 确实被前两个覆盖了 2 次，合法，点 3 只被 (2,4) 覆盖，也合法。可是如果贪心选不相交的区间，只能选 (1,3) 和 (3,5)，总长度也是 4，但这不是最优，因为开区间的情况下，三个区间可以同时选：点 2.5 被两个覆盖，点 3.5 被两个覆盖，没有任何点超过 2 层，总长度是 6。贪心按左端点排序、尽量选不重叠区间的做法，在这里直接吃瘪。

所以这个问题的难点在于 k 层的重叠限制。k=1 时就是经典的最大权不重叠区间选择，可以排序后 DP。k>1 时，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 的一条边。

离散化的细节很简单：

vector<int> 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 连到 i+1。这条边的含义是：车辆当前不选择任何区间，单纯从上一个关键时刻挪到下一个关键时刻。容量设 INF 是安全的，因为从源点总共只放了 k 个流量，网络中任意截面上的流量都不会超过 k，所以即使链边容量很大，实际流量也被源头限制住了。有人喜欢把链边容量设成 k，也能过，但没必要，反而容易让人误解。

第三类，每个区间对应的边。离散化后，左端点节点 u 到右端点节点 v，容量 1，费用为区间长度。容量 1 表示每个区间最多被选一次；费用为长度表示选中这个区间能获得的收益。如果题目改成求最多选多少个区间，费用改成 1 就行。

最后，最后一个关键点连到汇点 T，容量 k，费用 0，表示车辆到达终点，完成任务。

整个网络是一个非常简单的有向无环图结构：源点 → 第一个点 → 第二个点 → … → 最后一个点 → 汇点，中间穿插着一条条“跃迁边”表示区间。这种形态我习惯叫“链上搭边”。

2.3 容量和费用背后的“为什么”

很多初学者会问：为什么区间边容量一定是 1？反过来想，如果容量设成 INF，同一个区间可能被多个流量同时选择，相当于同一辆车重复跑同一段路，显然不合理。容量 1 保证了每个区间最多贡献一次费用。

为什么链边可以用 INF？因为链边对应“不选区间”的空驶状态，它不产生费用，即使多个流量同时走同一条链边也没关系，它们只是并行前进，不会改变覆盖计数。真正需要限制的是区间边和源点流量。

为什么要用最大费用流而不是最大流？因为我们的目标是收益最大，不是选得越多越好。网络流的“流量”只表示资源的数量，不直接表示收益；收益靠边上费用累积。最大费用流会在所有可行流里找费用最大的那个流量方案，正是我们要的答案。

还有一个细节：如果某个区间长度为 0，也就是 l==r，它的边会形成一个自环。自环在费用流里虽然不一定爆炸，但没有任何意义，还会让离散化 lower_bound 出现问题。读入时直接跳过 l>=r 的区间最省事。

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 参考实现（C++17）

下面给出一个完整的可提交代码。这份代码以开区间、长度为收益为默认模型，如果需要改成区间个数，把区间边的费用参数改成 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; vector<int> xs; vector<pair<int, 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)); queue<int> 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, r+1) 来表示闭区间覆盖。另一种做法是把所有端点坐标都乘 2，然后左端点用 2l，右端点用 2r+1，但这种方法写起来容易错，我更喜欢右端点加一。无论用哪种，都要时刻记住：网络流模型里每条边跨越的是“段”，不是“点”。建图前先确认题目给的是开区间还是闭区间，再决定要不要平移端点，这个习惯能帮你省下大量调试时间。

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。比如 k=2，有两个完全相同的区间 [1,5]，可以都选，覆盖 2 层，合法，收益叠加。
• 源点容量和汇点容量都设为 k。中间链边容量没限制。如果 k 很大，但可选的区间边有限，增广次数其实由有效区间数量决定，不用担心复杂度爆炸。
• 离散化后 m 可能很小。链边 O(m)，区间边 O(n)，总边数非常少。即使 n 上万，SPFA 也扛得住，因为增广次数被 k 限制。

4.4 一个“调包”技巧：数量版和权值版

这题最常见的变体是：不按区间长度算收益，而是问最多能选多少个区间，同样满足任意点覆盖不超过 k。这时候不需要改结构，把每条区间边的费用从 len 改成 1 即可。如果你做过“最长 k 可重区间集”，再遇到“最多 k 个不重叠区间”的版本，三分钟内就能改完。

另一种变体是线段集问题，即给定的是实轴上的线段而不是开区间，端点覆盖的判定规则可能不同。这种题可以沿用图模型，只需处理端点关系。你会发现，网络流的建图能力在于把“覆盖”这个操作抽象成“跨过一段弧”，弧的起点和终点只要定义清楚，模型就成立。

5. 延伸：从这道题看网络流的建图思维

5.1 和区间贪心的关系

当 k=1 时，最大权不重叠区间可以用 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 可重线段集”的时候，十分钟就建好了图。