做网络流建模题最怕什么不是Dinic写不出来也不是SPFA死循环而是图建不出来。“最长k可重区间集问题”恰好是训练一个人从“背模板”跨到“设计建模”的经典门槛。给定一堆区间每个区间有权值通常是长度你要选出一部分区间使得数轴上任意一点最多被“覆盖”k次目标是让选出的区间总权值和最大。听起来像贪心像DP但k一变大就全部失效。我当年第一次遇到这道题想了一晚上没头绪第二天看到“容量为k的源点”这个操作直接拍大腿。这篇文章想把整个建模思路彻底拆开为什么这样画图、四条边分别干什么、模板怎么写、有哪些坑是网上教程不会告诉你的。适合刚开始学费用流的人也适合想把自己从“会写模板”提升到“会设计网络流”的人。1. 先看懂题目区间、权值与“k重”到底限制了什么1.1 用一句话翻译题目给定n个区间比如[1,5]、[2,4]、[4,7]。每个区间的权值就是长度比如[1,5]权值是4。你需要选一个子集满足数轴上的任意一个点最多被k个选中的区间覆盖。求最大总权值。k1时问题就是“选一组互不重叠的区间让总长度最大”这个经典排序后DP就能做。k2时允许两个区间在同一个位置重叠但不能有三个。k3就允许三层。你可以把k理解成“同一时刻最多能有几个任务在进行”这就是典型的资源调度模型。1.2 为什么贪心和普通DP在这里吃瘪k1的时候区间按右端点排序维护dp[i] max(dp[i-1], dp[pre[i]] w[i])就能秒掉。但k2呢你需要在“当前点被覆盖了几次”这个维度上记状态区间端点一多状态直接爆炸。贪心按权值从大到小选也不行因为一个大权值区间可能把后面好几个中等权值区间的路堵死k重限制下做局部决策没有“最优子结构”保证。所以这题真正的解法不是加一维DP而是换一套世界观把“选区间”翻译成“在网络流里输送流量”。1.3 换一种世界观把数轴看成一条高速公路我理解这个模型的最舒服方式是把它想象成一条高速公路从起点到终点有k条车道。每个区间就是一条“上桥匝道”你开上去走一段到区间右端点再下来。限制“任意点最多被覆盖k次”翻译过来就是高速公路任意路段上同时行驶的车不能超过k辆。而“总长度最大”就是这些车在高速上行驶的总里程最大。网络流里那个流量就是车的数量。容量限制就是车道数。费用就是行驶里程。这个类比能解释后面所有建图决策。2. 建图拆解四条边各司其职2.1 第一步离散化因为坐标再大也不用怕区间端点可能到10^9但最多只有n个区间端点总数不超过2n。先把所有左端点和右端点取出来排序去重得到一串坐标。离散化之后数轴被切成了若干段每一段的宽度不重要重要的是这些段两两之间的顺序关系。离散化这一步看似不起眼但它是整个建模的地基。没有它你没法把“数轴上连续的一段”变成“图上相邻节点之间的一条边”。我习惯把第i个离散化后的点记为i最后点数m不超过2n2费用流跑起来非常舒服。2.2 骨架边相邻点之间的“直行车道”离散化后从小到大给每个点编号0, 1, 2, ..., m-1。然后在每个相邻点i到i1之间连一条容量很大、费用为0的边。这条边是什么它就是高速公路上“不选任何区间单纯向前行驶”的直行车道。流量从i流到i1表示这条路径在这一段没有覆盖任何区间所以费用是0。容量为什么大因为k辆车可以同时在这条骨架上行驶容量至少设为k就好完全没有必要开成无穷大后面代码里我会给一个比较稳的设定。2.3 区间边容量为1的“区间匝道”对于每个原始区间[l, r]找到l和r离散化后的编号u和v在u到v之间连一条容量为1、费用为区间长度r-l的边。这就是“选择这个区间”的动作。容量为1保证每个区间最多被选一次。费用为正表示选它能获得收益。流量从u走到v等于一辆车在这个区间位置离开骨架走了一段区间匝道到下端点回归骨架。关键是这条边是“跳”过去的中间那些骨架边它都不走这样才能表示“这个区间覆盖了这一整段”。2.4 源汇容量k的收口超级源点s连向离散化后的第一个点0容量为k费用为0。最后一个离散点m-1连向超级汇点t容量为k费用为0。这k的容量就是题目里的“k重”。因为从s只能流出k辆车整张图里同时存在的流量路径至多k条任意路段上覆盖数自然不超过k。你可以把s - 0理解成高速入口只允许k辆车上路m-1 - t理解成出口。2.5 把整张图的边表列出来对照建图这件事信息一多就容易乱。我每次写这种题都会先列一张表再动手敲代码边类型起点终点容量费用含义源边s离散点0k0k辆车进入高速骨架边离散点i离散点i1k0直行不选区间区间边离散点u离散点v1r-l选这个区间汇边离散点m-1tk0k辆车离开高速画完这张表你的建图代码基本就是照着抄。3. 为什么这张图是对的正确性的两个关键视角3.1 从流量守恒看“k重覆盖”很多人建完图还是心虚凭什么这个流对应合法方案我来给一个很直观的守恒论证。取任意一小段数轴也就是离散化后相邻两个点之间的那段开区间。任何从s到t的流量要到达t都必须穿过这一段从左侧的点到右侧的点。由于总流量是k那么穿过这一段的流量总数恰好是k。穿过这一段有几种方式要么走骨架边费用0要么走某一条区间边费用是区间长度同时代表这个区间覆盖了这一段。既然总流量固定是k那么覆盖这一段的区间边数量不可能超过k。这就天然满足了“任意点最多覆盖k次”的限制。反过来一个单位流量走区间边就获得对应费用费用最大化的目标自然就对应总覆盖长度最大化。我第一次想通这个“割”的说法时特别爽因为它把题目里最不好处理的连续覆盖限制变成了流量流过一个割的必然结果。流量必须过去但受到源点容量k的限制所以覆盖数被压在k以内。3.2 反向构造合法方案一定对应一个流另一个方向也要想清楚给定任意一组合法的区间选择方案能不能在网络流里构造出费用相同的可行流可以而且构造方式就是给区间“染色”。因为任意点覆盖不超过k这些区间作为区间图可以用不超过k种颜色染色使得同色区间互不重叠。这个结论是区间图的经典性质贪心按左端点排序就能实现。染完色之后每种颜色的区间构成一条时间线从s出发沿骨架边到第一个区间左端点走区间边跳到右端点再沿骨架边走直到t。每条颜色对应一个单位的流量k个颜色叠加起来就是一个流量恰好为k的可行流费用等于选中区间的权值和。所以最优流和最优方案是同一个对象最大费用流的答案就是题目答案。这个双向论证做完你在心里才敢真正信这个建模。3.3 最大费用流为什么不会“随便乱选”还有一个细节区间权值是正数最大费用流每次增广都会尽可能找总费用最高的路径直到不存在能增加总费用的路径。因为任何一条增广路本质是从s到t的一条路径如果它经过的区间边都是正权那路径费用就是这些选区的总长度。那会不会出现一条路径经过了好几个区间但中间夹着一小段骨架边完全可能。比如一个区间结束于某个点另一个区间从同一点往后开始它们的区间边就能在同一条路径上首尾相接。这也符合“k1时选互不重叠区间”的直觉。4. 代码实现模板、细节与踩坑全记录4.1 用SPFA求最长路一次增广到底费用流最常用的实现是“SPFA找最短路 沿最短路增广”。但这个题是最大费用两种做法第一种直接把所有边费用取负跑最小费用最大流最后答案取负。这是很多人的习惯因为最小费用流的SPFA判断条件写起来顺手。第二种直接SPFA找最长路每次增广时dis[v] dis[u] w就松弛最后累加dis[t]。我更喜欢这个写法不用动费用符号逻辑更直观。下面是核心模板基于第二种写法#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 2000; struct Edge { int to, cap, cost, next; } e[MAXN * 5]; int head[MAXN], cnt; void addEdge(int u, int v, int cap, int cost) { e[cnt] {v, cap, cost, head[u]}; head[u] cnt; e[cnt] {u, 0, -cost, head[v]}; head[v] cnt; } int dis[MAXN], pre[MAXN], preEdge[MAXN], flow[MAXN]; bool inq[MAXN]; bool spfa(int s, int t) { memset(dis, -0x3f, sizeof(dis)); memset(inq, false, sizeof(inq)); queueint q; dis[s] 0; flow[s] INF; pre[t] -1; 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].next) { int v e[i].to; 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; flow[v] min(flow[u], e[i].cap); if (!inq[v]) { q.push(v); inq[v] true; } } } } return pre[t] ! -1; } int maxCostFlow(int s, int t) { int maxCost 0; while (spfa(s, t) dis[t] 0) { int f flow[t]; for (int v t; v ! s; v pre[v]) { int i preEdge[v]; e[i].cap - f; e[i ^ 1].cap f; } maxCost f * dis[t]; } return maxCost; }一个关键点在第while循环的判断dis[t] 0。因为所有区间权值非负如果增广路径的总费用已经小于等于0再增广只会让答案变小直接退出。这个判断不加也能ac很多题但加了更严谨尤其是当你把模板拿去处理带负权区间的情况时。4.2 主函数读入、离散化、建图、跑答案我按自己比赛时的习惯写主函数带注释方便直接抄int main() { int n, k; cin n k; vectorpairint, int seg(n); vectorint xs; for (int i 0; i n; i) { int l, r; cin l r; seg[i] {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 m, t m 1; memset(head, -1, sizeof(head)); cnt 0; addEdge(s, 0, k, 0); for (int i 0; i m - 1; i) { addEdge(i, i 1, k, 0); } addEdge(m - 1, t, k, 0); for (auto p : seg) { int u lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(); int v lower_bound(xs.begin(), xs.end(), p.second) - xs.begin(); if (u v) continue; addEdge(u, v, 1, p.second - p.first); } cout maxCostFlow(s, t) endl; return 0; }骨架边的容量为什么设成k而不是INF因为s最多流出k个单位的流量任意一条边上的流量都不可能超过k你写INF也work但写k更清醒它时刻提醒你流量上限就是k。4.3 两个方向想用最小费用流模板怎么办如果你手里只有最小费用流的模板改起来很容易建图时区间边费用存成长度的相反数骨架边仍为0跑完最小费用流答案取负输出。注意你的最小费用流模板也要加一个“最短路径费用非负才增广”的退出条件否则会把负费用的垃圾路径也算进来。我个人的建议是这种“最大费用”题目最好专门存一个SPFA最长路模板。因为取负之后你在update边的时候容易把符号搞混排查起来费时间。一次写对最长路后面所有类似题都能复用。4.4 手推一个小样例验证建模纸上跑一个小数据比直接提交安心得多。假设k2区间如下[1,3] 权2[2,5] 权3[3,6] 权3[4,5] 权1离散化后点是1,2,3,4,5,6编号0到5。源点连0容量2骨架边0-1-2-3-4-5容量2费用05连汇点容量2。区间边分别为0-2容量1费用21-4容量1费用32-5容量1费用33-4容量1费用1。第一次SPFA最长路找哪条0-1-4-5走区间[2,5]费用3。第二次反向边出现但是最大费用流沿新路径走比如0-2走[1,3]费用2再2-5走[3,6]费用3总费用5。两次增广流量一共2总费用8。实际最优选[1,3]和[3,6]、还有[4,5]不流量已经满了不能再选。其实还可以选[1,3][3,6][4,5]? [4,5]与[3,6]在[4,5]重叠[1,3]不相交任意点最多2重[4,5]处有[3,6]和[4,5]两重合法总权2316比8小。所以8就是最优。你可以自己按这个流程再推一遍建图的每一步都会变得很具体。5. 高频问题速查这些坑我全踩过5.1 区间端点重叠到底算不算超过k这是最容易含糊的地方。如果题目定义是“开区间”那[1,3]和[3,6]可以同时选重叠的点3不算覆盖。如果题目定义是“闭区间”那么点3同时被两个区间覆盖k1时这俩就不能同时选。大部分“最长k可重区间集”的题目按开区间处理即覆盖长度只看右端点减左端点。如果你拿到的是闭区间版本有个简单改法离散化的时候把所有右端点改成r1区间边从ul的编号连到vr1的编号费用仍然用r-l。这样端点重叠就被正确地区分开了。我看到好几个人在这里卡样例问题全出在端点上。5.2 如果权值不是区间长度怎么办题目里的费用完全可以是任意给定的正数。比如每个区间给你一个“价值”和长度无关。处理方式零改动建区间边的时候费用填那个价值就行。只要满足“任意点覆盖不超过k”的限制费用随便给网络流都能处理。如果权值可能是负数也不慌。负权区间边在最大费用流里不会被正收益路径选中因为绕开它走骨架边费用更高。只要SPFA的dis[t] 0判断写对了答案依然正确。5.3 k1的时候网络流会不会太慢会但不至于不能用。k1的时候这个问题等价于最大权不相交区间集排序后DP是O(n log n)网络流是O(n * 最短路)量级慢不少。如果题目明确k1别秀建模老老实实用DP。但k2、k3甚至kn时网络流复杂度基本不变DP则彻底没法做。这也是这个建模存在的意义它把“k”变成了源点容量复杂度不随k爆炸。5.4 姊妹题最长k可重线段集问题网络流24题里还有个“最长k可重线段集”区间换成线段每条线段有斜率横坐标跨度不再是费用而是线段长度。这类题在“垂直方向”多了一层处理需要拆点或者建立更复杂的层次图。原理其实还是同一个只是每条“线段”在数轴上可能跨越得很厉害你需要在建图时额外判断。如果你把本文的区间建模吃透再看线段版就不会觉得是全新题顶多是原题加了点几何外壳。5.5 同系列其他题目帮你横向理解网络流24题里“飞行员配对”是二分图最大匹配教你识别“人和岗位”的冲突“方格取数”是二分图点权独立集教你用最小割处理互斥“太空飞行计划”是最大权闭合图教你用最小割处理依赖关系。而这个“最长k可重区间集”教你的核心思想是连续数轴上的覆盖次数限制可以被等价建成一条链式骨架上的容量限制。这四道题做完你对网络流建模的感觉会有一个质的飞跃。它们的共通点都是找到一个“流量必须流经某个割”的约束然后再把目标翻译成费用。6. 一些我后来才想明白的建模心得第一次看到这个题的建图我以为是某个大佬灵光一闪的构造。后来刷多了才发现它是一个可复用的“模板思维”当题目出现“任意一个位置最多容纳k件事”的时候立刻想到用k容量作为源点边界用一条从左到右的主链当作时间轴每件事就是一条带费用的跨越边。这个套路能解的题非常多排工单、选区间、规划行程都能套。另外一个小技巧手写SPFA跑费用流遇到状态不对别急着debug先把图打出来。我写了一个简单的打印函数把边的起点、终点、容量、费用全部输出对着样例手推一遍。大多数时候问题不是模板错了而是你连边的方向或者容量设错了。尤其是离散化映射我犯过至少三次“忘记用lower_bound取编号”的低级错误。写图论题别怕慢别怕画。你花半小时把图推清楚比提交十次试错要快得多。