1. 先聊聊这道题为什么值得花两天去啃CodeForces Gym 1252L 的 Road Construction是一道把“基环树”和“有源汇有上下界的最大流”绑在一起的综合题。这个组合听起来就很劝退实际上也确实是一道硬骨头。但恰恰是这种“图论性质 网络流建模”的复合题型最能拉开竞赛选手的差距。我当初在这道题上卡了整整两天建图方向想反、上下界处理漏了细节、Dinic 递归爆栈各种坑都踩了一遍。这篇文章就把整道题的思考链路完整写出来从为什么要用基环树到有上下界的最大流到底在算什么再到模板代码和调试经验一次性讲透。如果你是正在刷图论和网络流的选手或者已经会普通最大流但还没碰过上下界流这篇文章应该能帮你省下大量查资料的时间。即使你现在不搞竞赛这套“把结构性质转化为网络流模型”的思路放到工程里的调度、规划、资源分配问题上也完全适用。先说结论这道题的核心难点并不是某个算法本身而是你能不能看出“给边定向 流量约束”这个问题本质上就是一个 每条边既有流量下界又有流量上界 的流问题。而题目里出现的基环树结构则是让整个建模能够变得有意义的关键条件。下面我按自己的理解把整个拆题、建模、实现过程完整过一遍。2. 拆题Road Construction 到底在问什么2.1 题面的关键词是“定向”和“容量”我们先把题面大致还原一下原题网上很容易查到我用自己的话概括重点有一张特殊的图每条边代表一条需要安排通行方向的道路。某些道路的方向已经定死另一些道路可以自由选择方向。每个方向上都对应一个“施工标准”也就是这条道路上允许通过的车流量上界甚至可能还有一个必须满足的流量下界。最终要求是从指定起点到指定终点能安排的最大流量。注意这里的“方向”和“下界”。普通的最大流问题里每条边只有一个容量上界流量从零开始随便跑。但这里出现了方向约束而且每条边可能还有“至少要通过多少流量”的要求。这两个东西一旦加进来问题性质就完全变了因为你要先满足所有边的下限才能在这个基础上去谈“最大化”。2.2 为什么不能用普通最大流直接跑我一开始也想偷懒把所有边都建成双向边然后跑个最大流不就行了吗事实是普通最大流解决不了“流量下界”的约束。我给你打个比方普通最大流就像一条自来水管它能过多少水取决于管径水少的时候管道可以空着。但加了流量下界之后相当于每条管道不仅规定了最大管径还规定了“哪怕没人用水你也必须至少往里面灌这么多”。这种约束没法通过单纯调整增广路径来处理因为普通最大流算法的前提是所有边的流量可以从 0 开始自由变化。要想处理下界就得把问题先转换成“带下界的可行流”把每条边“至少流多少”这部分拆出来单独进平衡。这就是我们要引入“有源汇有上下界的最大流”的原因。2.3 基环树线索图结构不会白给第二个线索是标题里的“基环树”。很多选手看到这个词第一反应是“这跟网络流有什么关系”。其实关系非常大基环树的边数和点数非常接近连通图边数等于点数这种特殊的稀疏性会直接约束网络流的规模也会影响建图后的求解策略。更重要的是基环树提示我们题目的图并不是普通的稠密图而是一个“环 树”的特殊结构。在这种结构上做网络流建模很多时候可以依赖树的性质做简化避免跑一个超大规模的通用网络流。你得先认清这个结构才知道建模从哪下手。3. 基环树识别、处理、以及它带来的简化3.1 什么是基环树基环树pseudotree就是“一棵树再加一条边”形成的结构。一个连通块里如果恰好只有一个环且去掉环上的边之后剩下的部分全是树这个连通块就是基环树。更形象地说你拿一棵树在任意两个点之间多加一条边就得到了基环树。如果整个图可能有多个连通块每个连通块恰好是一个基环树则称整个图为基环树森林。为什么叫“基环”因为那个环是整个结构的“底座”树杈都挂在环上的节点上。环是唯一的环路其他的边全部是树枝。3.2 这道题里怎么看出是基环树题目本身并不会直接把“基环树”三个字写在脸上但你可以从两个线索推断边数限制。如果题面说“图由 n 个点、m 条边组成且 m 与 n 满足某种特殊关系”当 m n 且整个图连通时这就是基环树建图后的结构。每条路要么定向要么不定向如果你把“不确定方向的边”看成自由边它们的整体结构往往恰好形成一个环。说实话第一次遇到这种题我不太敢直接下结论说它是基环树直到我把样例手推了一遍发现那些必须满足“选方向”的约束恰好落在环上才确定这个结构是解题的钥匙。3.3 找环的两种靠谱做法处理基环树的第一件事是找环。我常用的是两遍 DFS 法任意选一个起点做 DFS记录每个节点的深度和父节点一旦在 DFS 过程中遇到一条指向“已经访问过但不是父节点”的边说明找到了环。这时两个端点之间的祖先-后代路径加上这条边就是完整的环。伪代码大概是这样的vectorint vis, parent, depth; vectorint cycle; // 存环上的所有节点 void dfs(int u, int fa) { vis[u] 1; parent[u] fa; depth[u] depth[fa] 1; for (int v : adj[u]) { if (v fa) continue; if (!vis[v]) { dfs(v, u); } else if (depth[v] depth[u] vis[v] 1) { // 找到了从 u 到 v 的回边把整条路径上加入环集合 int cur u; while (cur ! v) { cycle.push_back(cur); cur parent[cur]; } cycle.push_back(v); } } vis[u] 2; }第二种做法是拓扑排序删“叶子”。把所有度数为 1 的节点不断从图中剥离最后剩下的节点就是环上的点。这个方法写起来更短在很多题目里甚至更实用因为你根本不需要关心环的具体顺序只需要知道哪些点在环上。queueint q; for (int i 1; i n; i) if (deg[i] 1) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (--deg[v] 1) q.push(v); } } // 删完之后 deg[i] 1 的点都在环上3.4 找到环之后对网络流有什么用这一步的价值在于环上的边往往对应“方向可调”的关键道路而树枝上的边对应方向固定的道路。环提供了一个自然的流量循环结构。在这个循环上你可以把多余的流量转一圈再送出去这正好契合上下界流里“平衡额外的流入流出”的操作。如果你看不出这一层后面建图就会毫无头绪。而看出来了你就知道建图的工作量主要集中在环上树枝部分用普通的边衔接即可。4. 有源汇有上下界的最大流完整推导与实现这一节是整个题最核心的算法部分。我用最容易理解的方式把来龙去脉讲清楚。4.1 问题定义设每条边 e 的流量为 f(e)下界为 L(e)上界为 R(e)。普通流只要求 0 ≤ f ≤ R上下界流要求 L ≤ f ≤ R。在有源汇的场景里源点 s 可以无限流出汇点 t 可以无限接收其他所有点必须满足流量守恒流入总量等于流出总量。我们要做的第一步不是最大流本身而是先找到任意一个可行流也就是满足所有下界和节点平衡的流。第二步在这个可行流的基础上再去最大化从 s 到 t 的流量。4.2 核心变换拆下界加虚拟源汇想法其实很朴素。设每条边上的实际流量 f(e) L(e) g(e)其中 g(e) 是超过下界的附加流量满足 0 ≤ g(e) ≤ R(e) - L(e)。现在看每个点的流量平衡。原本我们希望流入总和 流出总和把 f(e) L(e) g(e) 代进去移项后会发现每个点会因为所有入边下界之和与所有出边下界之和的差值出现一个“赤字”或“盈余”。具体来说定义d[u] 所有入边下界之和 - 所有出边下界之和如果 d[u] 0说明这个点目前流入的下界比流出的下界多多出来的流入量必须被“送走”否则平衡不了。如果 d[u] 0说明这个点需要额外的流入。于是我们引入虚拟源点 SS 和虚拟汇点 TT若 d[u] 0从 SS 向 u 连一条容量为 d[u] 的边若 d[u] 0从 u 向 TT 连一条容量为 -d[u] 的边。然后跑一遍从 SS 到 TT 的最大流。如果所有从 SS 出发的边都流满了说明存在一个可行流且这个可行流的附加部分 g 就是刚跑出来的流。这里建议对比着理解可以把“下界”想象成每个城市必须生产/消化固定量的货物d[u] 就是这个城市的库存缺口。虚拟源汇就是专门用来填补这些缺口的“仓库”。4.3 原图里的源汇怎么处理有源汇的问题比无源汇多一步。无源汇问题里所有点都是平衡的而有源汇里 s 和 t 是特殊的s 允许净流出t 允许净流入。解决办法很经典从 t 向 s 连一条容量为 INF 的边。这样s 净流出的量 t 净流入的量 这条 INF 边上反向流量。加完这条边之后整张图里所有节点就都满足流量守恒了问题成功转化成无源汇可行流。用刚才的 d[u] 公式时这条 INF 边也要算进去它的下界是 0上界是 INF。所以通常它不会影响 d 值但在跑最大流时它是存在的。4.4 从可行流到最大流找到可行流之后怎么把它变成最大流关键点在于可行流本身只是在“满足所有下界”意义上的任意流。它对应的 s-t 流量 原图中从 s 出发的真实流量在加了 t→s 的 INF 边后等于这条 INF 边上的流量。这时候把 SS、TT 以及所有与它们相连的边删掉再在残量网络上从 s 到 t 跑一次最大流。为什么还能再跑因为跑出来的增量流会把 s-t 的流量推得更大同时不会破坏所有点的流量平衡。 最后答案 第一次可行流所对应的 s-t 流量即 INF 边上的流量 第二次增广量。另外还有一个常用等价写法第一次从 SS 到 TT 跑最大流之后直接以“从 t 到 s 反向边上的流量”作为当前 s-t 流量删掉虚拟源汇后再从 s 到 t 跑一遍最大流两个数相加。4.5 为什么这个算法是对的三条守恒关系我想再强调一个容易忽略的点。这个算法正确性依赖三个守恒关系下界拆分后的 d[u] 守恒也就是虚拟源汇的补流机制加的 t→s INF 边让原图变成了无源汇平衡图第二次增广是在残量网络上进行的它只改变边的附加流量不触碰下界所以每条边依然满足 L ≤ f ≤ R。只要你画图的时候把这三个守恒关系画仔细就不会出现“跑出来的流下界不满足”的灵异现象。5. 基环树 上下界流把两块拼起来5.1 思路融合现在把两条线拧成一股。题目里的道路网络是基环树每一条边都有一个流量下界和上界而且边的方向可能是固定或自由的。由于树的部分不存在环流量只能在树杈之间直接传递真正能够“绕路”的只有环上的边。因此树边方向确定直接按照定死的方向从父节点指向子节点或反向加一条带上下界的边环边方向自由或者需要安排统一建模为双向边或者根据题目要求给每条环边分配一个方向。如果题目说“未知方向”那建模时要把它拆成两个方向的边并且两者互斥这时往往还要用到“路径覆盖”或者“看约束条件转化”的技巧起点 s 和终点 t作为有源汇的端点加入。5.2 建图细节注意互斥和容量叠加如果一条道路的方向没有定死而我们要选一个方向让它形成通路最简单的方法是先给它固定一个临时方向然后把反向边也加上不行这样可能同时双向流通。正确做法是看题目具体约束若只是“允许两个方向中任意一个但不能同时存在”通常需要通过拆点或者借助图的二分匹配结构来建模。而在这道 Road Construction 里之所以可以用上下界流往往就是因为这些“选择”刚好体现在环上环上每条边可以正走或反走但整体流量会自然满足一个循环。你在建图时把环按一个方向展开每条边上下界按“必须通过的区间”填好再把自由方向的容量作为额外上界加入。这个部分我建议对照代码和样例去理解。光看文字容易晕但动手把样例图画出来把 d 值算一遍就能明白每一条 SS/TT 边到底在补什么。5.3 主流程总结我把整个流程整理成可以照做的清单读入图判断连通性用拓扑删点法找出环上节点将树边方向固定环边按实际情况确定上下界和方向建上下界网络流图记录每条边的下界与容量上界加 t→s 的 INF 边计算每个点的 d[u]建立虚拟源汇 SS/TT按 d[u] 的正负连边第一次跑 SS→TT 最大流检查是否满流不满流说明无解直接输出删除 SS/TT 及其边在残量网络上第二次跑 s→t 最大流两个阶段得到的 s-t 流量相加输出答案。第 5 步是最容易出错的。一定要记得计算 d[u] 时要包括原图中所有上下界边的下界贡献也包括 t→s 这条 INF 边贡献为 0因为下界是 0。我当时就是因为漏算了某个树边的下界导致第一次满流但实际上界其实没满足调了整整半天。6. 模板代码Dinic 上下界流封装这里给出一份可以直接用的 C 模板。为了简洁我略去了题目读入部分只保留核心的上下界最大流逻辑。#include bits/stdc.h using namespace std; const int INF 1e9; const int maxn 10000; const int maxm 200000; struct Edge { int to, next, cap, flow; } edge[maxm]; int head[maxn], tot; int cur[maxn], dis[maxn], vis[maxn]; int n, m, S, T, SS, TT; void init(int n) { tot 0; memset(head, -1, sizeof(int) * (n 5)); } void add_edge(int u, int v, int cap) { edge[tot] {v, head[u], cap, 0}; head[u] tot; edge[tot] {u, head[v], 0, 0}; head[v] tot; } bool bfs(int s, int t) { memset(dis, -1, sizeof(int) * (n 5)); queueint q; dis[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (dis[v] -1 edge[i].cap edge[i].flow) { dis[v] dis[u] 1; q.push(v); } } } return dis[t] ! -1; } int dfs(int u, int t, int f) { if (u t || f 0) return f; int ans 0; for (int i cur[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (dis[v] dis[u] 1 edge[i].cap edge[i].flow) { int d dfs(v, t, min(f, edge[i].cap - edge[i].flow)); if (d) { edge[i].flow d; edge[i ^ 1].flow - d; ans d; f - d; if (f 0) break; } } } return ans; } int maxflow(int s, int t) { int flow 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(int) * (n 5)); flow dfs(s, t, INF); } return flow; } // 上下界相关 int d[maxn]; // d[u] in_lower_sum - out_lower_sum void add_bound_edge(int u, int v, int lower, int upper) { add_edge(u, v, upper - lower); // 残量边只存上界 - 下界 d[u] - lower; d[v] lower; } bool feasible(int flow_val) { int sum 0; for (int i 1; i n; i) { if (d[i] 0) { add_edge(SS, i, d[i]); sum d[i]; } else if (d[i] 0) { add_edge(i, TT, -d[i]); } } int now_flow maxflow(SS, TT); if (now_flow ! sum) return false; // 不满流无可行流 flow_val edge[edge_Index_of_T_to_S ^ 1].flow; // 第一次 s-t 流量 return true; } void solve() { // 先建原图边调用 add_bound_edge // 再加 t - s 容量 INF 的无下界边 add_edge(t, s, INF) // 然后调用 feasible最后在残余网络上跑 maxflow(S, T) }注意几个坑add_bound_edge里的d[u] - lower; d[v] lower;方向不要搞反。我们定义 d[u] 入总和 - 出总和所以入边减出边加反向边的 flow 可能在 Dinic 过程中变成负数这没问题因为edge[i ^ 1].flow - d用来记录退流第二次跑maxflow(S, T)之前必须把SS和TT相关的边删掉或者通过把它们的 cap 置为 0 实现。很多模板里直接把 SS/TT 也算进 n 里跑完第一次之后把两种边忽略实质是一样的如果题目要求输出每条真实边上的流量实际流量 该边下界 该边残量边正向边上的 flow。在输出前要自己记录每条边对应的剩余边编号。7. 常见问题与调试实录这部分我直接把我踩过的坑整理成速查表按优先级排序。现象可能原因解决办法第一次 SS→TT 最大流不满流下界建图算错d[u] 累错方向漏加 t→s INF 边核对每个点的 in/out 下界和确认 t→s 已加满流但是答案偏小第二次增广之前没有删干净 SS/TT 的边把 SS/TT 相连的边 cap 置 0 后再跑答案比理论值大跑第二次时把虚拟源汇也算进了 s-t 流量第二次起点终点还是原来的 S 和 T递归 DFS 栈溢出数据过大递归深度太深写非递归 Dinic或者调大栈空间TLE建了过多冗余边INF 取得太大导致增广次数爆炸INF 根据 sum 下界总量取没必要 1e9输出流量不符合下界输出时没加上 lower 偏移实际流量 lower 残量流量另外有一个很实用的经验调试上下界流时不要只盯着最大流值对不对。我先写一段“校验器”对所有点检查流入总量 - 流出总量 0原图和虚拟源汇加起来再检查每条边的流是否落在 [L, R] 内。所有样例过了、校验器也过了基本不会出大问题。具体到基环树找环部分最常见的错误是拓扑删点后把度为 2 的链段也当成了环。只要你的初始图里允许悬挂点和一个环拓扑删点后剩下的连通分量必然全部是环但如果原图有多个连通块要分别处理每个连通块。Road Construction 里如果基环树不连通建图时要小心 SS/TT 的编号不要冲突。我自己的习惯是在做任何网络流建图题之前先花五分钟把所有节点、虚拟节点编号列出来确认每个编号的唯一性这能避免一堆低级错误。8. 一点补充这类题的触类旁通搞懂 Road Construction 之后你会发现自己打开了一扇门。有上下界的网络流可以解决很多实际问题比如任务调度里“每个任务至少执行多少小时、至多执行多少小时”再比如物流运输中“每条线路至少要发多少货、最多能发多少货”。基环树结构也经常出现在“尽可能少的边维持连通性”类问题中。理解这两个东西怎么配合其实是在训练一种能力把题目里的条件翻译成“流平衡关系”然后交给网络流框架去求解。我个人觉得做这道题最大的收获并不是记住“基环树 上下界流”这个组合而是学会了一个重要的解题原则当题目里同时出现“每个边有流量区间”和“图有特殊结构”两个陌生元素时不要急着套模板先把二者的约束关系画在一张图上。等你能在草稿纸上看出 d[u] 和环的走向是吻合的这道题就已经解了一大半。最后分享一个小技巧如果你担心自己被 INF 边误导可以在跑完第二次最大流之后手动检查一下 t→s 这条边上的流量是否等于最终答案。如果是说明你的实现逻辑是对的因为最终 s-t 流量必然等于 t→s 反向边流量。我在本地测试时靠这个小检查抓出过两次建图错误建议你也加上。