第一次做 Codeforces 1252L Road Construction 的时候我其实是被题解标题里的两个词同时劝退的基环树、有源汇有上下界的最大流。前者还能靠画图硬啃后者光是“上下界”三个字就让很多人直接右上角。真正沉下心把这题做完之后我的感受是它其实是把两个单独都不算太友好的知识点用一道题串成了一条非常标准的解题链。这道题的内核可以粗暴地概括为一句话在一棵基环树上选若干条边每个点的最终度数必须落在一个给定区间里问是否存在方案或者最多能选多少条。外壳是修路建桥内壳是网络流建模。适合的读者是已经会 Dinic 最大流、对网络流建模有基本感觉但还没系统接触过上下界流或者刷了不少树题却不知道怎么和流结合的人。如果你只是想背模板看完第三节就能拿走一个可以直接改着用的框架如果你想弄懂为什么这里要绕这么大一圈那建议从头看。先说结论这题不需要什么玄学核心就三步——把图还原成基环树、把度约束写成上下界、把存在性/最大化问题丢给最大流。下面我把每一步里我当初没想通的地方都展开说。1. 拆题Road Construction到底在问什么1.1 外壳是修路内核是“选边满足约束”题目叫 Road Construction但竞赛题里名字越接地气抽象程度往往越高。修路建桥只是故事背景真正的问题通常是这样给你若干个点点之间有若干条候选边其中一部分边是“必须修”的另一部分是“可选修”的同时每个点有一个度数限制最低连多少条、最高连多少条。把“城市”换成节点“道路”换成边“必须修/可选修”换成边上的下界/上界这就在网络流里非常眼熟了。每个节点的度数下限就是流入这个点的流量下界度数上限就是流量上界。选择某些边修建等价于在这些边上安排流量最终能不能让所有点的流量都落在自己的区间里就是一个存在性问题。如果还要求“最多能修多少条可选边”那就是最大化问题。我第一次见这题时脑子里只有普通最大流于是很自然地想把每条边容量设为 1源点连向所有点所有点连向汇点跑一发不就行了但这样做根本处理不了“下界”约束。普通的 Dinic 只能表达“最多流多少”表达不了“最少必须流多少”。这就是上下界流登场的根本原因。1.2 为什么要强调“基环树”而不是泛泛的图如果题目给的是普普通通的稀疏图那这个建模会变成一个规模很大的网络流问题虽然也能跑但出题人不会把它放在一个以树结构为背景的题里。标题特意点出“基环树”说明原图中的可选边和必须边组合起来恰好构成一棵树加一条边。基环树的特殊之处在于它只有一个环。树的部分没有回流自由度每条边的流量方向基本被树结构锁死而多出来的那条环边给了整个系统唯一的“循环自由度”。这个自由度在约束方程里表现为一个可以任意取值的环绕流量普通贪心很难处理它但上下界网络流天生就是处理“流量守恒 区间限制”的两者可以说是绝配。所以看到“基环树 有源汇有上下界的最大流”这个组合时思路应该自动弹出来先用基环树的结构把环找出来理解自由度在哪里再把所有约束写成上下界流模型用两次最大流解决存在性或最大化问题。下面分别拆开讲。2. 基环树找到环就找到了自由度的开关2.1 找环的两种写法基环树的环是一棵树加上一条额外边形成的唯一环。找环的姿势有很多我常用的有两种。第一种是拓扑删叶法。把所有度数为 1 的节点先扔进队列不断删除叶子最后剩下的节点一定都在环上。用并查集维护“是否还在图中”或者直接在原图上标记删除代码很短而且复杂度是 O(n)。第二种是并查集法。在读入边的时候如果一条边的两个端点已经在同一个集合里说明这条边就是形成环的那条“额外边”。记下这条边然后用 DFS 从其中一个端点出发沿着树边回到另一个端点路径上所有点加上这条额外边就是整个环。我个人的习惯是如果是基于邻接表建好图之后再找环用拓扑删叶法更顺手如果还在读入阶段就能判断“哪条边是最后一条”用并查集法更直接。两种写法都能在 O(n) 内完成不会成为瓶颈。2.2 环上的流量守恒意味着什么为什么环这么关键因为一条边的选择不是孤立的。假设我们在树上做一个度数约束那么每个非根节点的需求都会沿着树边向父节点传递最终汇总到根没有环的时候整个约束系统的解几乎是“一条道走到黑”的要么直接满足要么无解中间没有太多可调节的余地。一旦多出一条边形成环事情就变了环上的流量可以绕一圈回到起点形成一个不改变任何节点净流量的“循环流”。这个循环流的值是可变的它可以让某些边少修一点、某些边多修一点同时依然满足所有节点的度数范围。换句话说基环树给了整个问题一个连续的自由度而普通树上没有。在上下界网络流里这种“循环流”恰恰是核心概念。无源汇可行流问题本质上就是问能不能找到一组流量让每条边流量落在上下界内同时每个点都满足流量守恒基环树上的那个环和网络流里的循环流在数学上是同一个东西。这就是这两个知识点能合到一道题里的深层原因。2.3 为什么树边不能直接贪心有人可能会问树上的约束为什么不用树形 DP 或者贪心非要绕到网络流这是因为题目里不仅有树边还有那条环边而环边会把树结构的“局部最优”破坏掉。你可以在树的某个子树里贪心出最小流量但环边可能恰好需要子树让出一部分流量才能让整张图有解。更关键的是如果每个点的约束是上下界区间而不是单点值那么树边流量的可行范围是连续的。连续区间的组合问题用贪心很难处理因为一个节点的选择会影响祖先的一整条链而网络流把这种连锁影响变成了图上的一条条增广路反而更直接。我自己做这题时的体会是不要试图在树上做局部决策直接把整棵基环树翻译成网络让最大流去处理全局平衡。3. 有源汇有上下界的最大流先把下界“预支”掉3.1 直接跑 Dinic 会漏掉什么普通最大流模型里每条边有一个容量上限源点产生流量汇点吸收流量中间节点流量守恒。但“下界”约束意味着有些边即使没有流量经过也必须先贡献一部分流量。这部分流量虽然不经过源点但从守恒的角度看它已经改变了节点的净收支。举个例子一条边 u→v 的下界是 3那么就算你不想流它u 也已经“失去”了 3 个单位的容量空间v 已经“得到”了 3 个单位的流量。如果不做处理直接在原图上跑最大流这 3 个单位就凭空消失了节点守恒会被破坏。解决思路很朴素先把下界流量强制加上去然后再在剩余容量上跑普通最大流。这也是“预支下界”这个名字的由来。3.2 收支差 d[u] 与超源超汇具体做法是读入每条有向边 u→v下界 low上界 up。先在这条边上建立一个容量为 up-low 的边这是剩余的可调空间。同时维护每个节点的收支差out[u] 累加所有从 u 出发的边的下界之和in[v] 累加所有到达 v 的边的下界之和d[u] in[u] - out[u]。d[u] 的正负表示强制加上所有下界之后u 是多了流量还是少了流量。如果 d[u] 0说明 u 多收了流量需要把这些多出来的流量送出去于是从超级源 SS 连一条容量为 d[u] 的边到 u如果 d[u] 0说明 u 还欠着流量需要从 u 连一条容量为 -d[u] 的边到超级汇 TT。跑一遍 SS → TT 的最大流之后判断从 SS 出发的所有边是否都满流。如果满流说明存在一个可行流能够满足所有下界和守恒否则无解。3.3 有源汇转无源汇那条 t→s 的 INF 边上面的处理解决的是无源汇可行流问题也就是找不到一个明确的源点所有节点都只是流量守恒。但 Road Construction 这类题通常是有源汇的有一个起点和一个终点或者有一个明确的“总需求”要从源送到汇。处理方法是在原汇点 t 和原源点 s 之间连一条容量为 INF 的边。这样一来原本从 s 出发、最终到达 t 的流量可以通过这条边绕回 s整个网络就变成了一个巨大的循环网络可以用无源汇可行流的办法来判定。注意这条 t→s 的边不是障眼法它承载的流量恰好就是“从 s 到 t 的净流量”。第一次跑 SS → TT 最大流时如果可行t→s 边上一定获得了一个流量值这个值就是当前可行流里 s→t 的总流量。3.4 两次最大流的完整计算顺序有源汇有上下界的最大流最终答案不是一次最大流得出的而是要跑两遍按 3.2 的方式建图额外加入 t→s 容量 INF 的边跑一次 SS → TT 的最大流检查超源边是否满流不满则无可行解记下 t→s 边上实际流过的流量 flowA这是可行流里 s→t 的流量在残量网络上“撤掉”超级源 SS、超级汇 TT 以及它们的所有关联边再撤掉 t→s 那条 INF 边从 s 到 t 再跑一次普通最大流得到增量 flowB最终答案 flowA flowB。为什么要跑第二遍因为第一次跑出的可行流只是“满足所有下界的一个解”不代表 s→t 的流量最大。第一遍结束后残量网络里还有剩余的容量空间第二遍的作用就是把这些空间榨干。第一次的 flowA 是保底流量第二次的 flowB 是优化增量。3.5 一个最小的例子拿最简的图来说s1t2只有一条边 1→2下界 3上界 5。out[1] 3in[2] 3d[1] -3d[2] 3网络里只有一条边容量为 5-32加边 t→s容量 INFSS 向 2 连容量 3 的边1 向 TT 连容量 3 的边SS → 2 → 1 → TT 这条路径能流 3SS 边满流可行此时 t→s 边上的流量为 3即 flowA 3清掉 SS、TT 和 t→s 边后残量网络上 1→2 的剩余容量是 2从 s1 到 t2 再增广 2flowB 2答案 3 2 5。这个例子小到可以直接心算但把两次流的职责分得清清楚楚第一次保下界第二次冲上限。4. 回到 Road Construction基环树如何和网络流拼接4.1 度约束建模点容量与边选择题目的“每个点度数在 [L, R] 内”这个约束放到网络流里怎么表达常见的做法是把每条可选边看作 1 个单位的流量它能从某个方向穿过每个点的度数上限 R 就是这个点能接收的流量上限。如果分成“点容量”来限制一个直接的办法是拆点把每个点拆成入点和出点入点到出点连一条容量为 R 的边代表这个点最多处理这么多流量。下界 L 则作为这条拆点边的下界也就是说每个点至少要有 L 个单位的流量经过它。这种建模在一般网络流题里很常见但它会让节点数翻倍。Road Construction 这类基环树题往往不需要拆得这么复杂因为树的度数本身就是边数你可以直接给每条树边一个上下界区间把“点约束”转化成“与点相连的所有边流量之和落在区间内”。不过这种约束不在单条边上而在节点上所以通常还是需要拆点处理才严谨。我建议直接拆点虽然多一倍节点但模型清晰、不容易错。拆点之后基环树的每条树边在入点和出点之间都是一条普通边环上的那条额外边则作为连接两个环节点的特殊边进入网络。这样一来整张图的结构就和原题完全对应流量的含义就是“这条边是否被修建”。4.2 无向边为什么不能简单拆成两条边原题的路大概率是无向的修建一条路意味着两个方向的连通同时生效。但在网络流里你通常只能建两条方向相反的有向边这就会带来一个陷阱如果两条边都获得流量从外部看这条无向边似乎被“修了两次”但实际只能修一次。解决这类问题的标准姿势有很多种常见的一种是把一条无向边转换成一个中间点中间点连接两端的入点或出点容量都为 1这样无论从哪个方向流最终只消耗 1 个单位的流量。另一种更偷懒的方法是在建图时人为规定每条无向边只允许一个方向有流量用容量限制让反向边无法同时使用。Road Construction 题里的“选边”往往只需要判断“选 or 不选”所以用中间点法更稳妥不容易写出错模型。虽然节点数会多一些但基环树的边数本来就接近 O(n)多出来的中间点不会影响复杂度。4.3 环边的“自由环流”恰恰是上下界流的主场基环树上树边的流量可以看作“必须承担”的那部分它们沿着树的方向传递环边的存在让整个网络多了一个环绕变量。在上下界网络流中这个环绕变量不会破坏任何节点的守恒因为环流绕一圈净变化为零但它会占用每条环边的容量区间。换句话说环边就像一个“可调节的阀门”上下界流会自动找到一个合适的阀门位置让整张图可行。这也是为什么在网络流模型里你不需要额外枚举环边选或不选——流量本身会替你决定。第一次做这题时我甚至尝试过 DFS 枚举环边的选择状态然后在树上贪心判定结果代码写了一百多行还漏洞百出。换成上下界流之后只需把环边和树边一起丢进网络判定逻辑和最大化逻辑全部交给最大流代码长度反而下降了。这就是“模型正确”的威力。4.4 可行解与最大选择数的输出如果题目只问“是否存在修建方案”那么第一次 SS → TT 最大流满流就够用了直接输出 YES/NO。如果问“最多能额外修多少条可选边”就必须跑完整的两次最大流第一次得到一个满足所有下界的可行流第二次在残量网络上把 s→t 的流量继续增大flowA flowB 就是最大选择数。具体原题问的是哪一种需要读题确认但两次流的框架是通用的。我写代码时的习惯是把“跑第一次判定”和“跑第二次求最大”封装成同一个函数只在最后决定要不要执行第二步这样题面有任何小变体都能快速适配。5. Dinic 代码里那些让提交从 AC 变 WA 的细节5.1 满流判定别只看总流量第一次跑 SS → TT 的最大流之后判断可行性的标准是“从 SS 出发的所有边全部满流”。很多人的第一反应是拿总流量和 SS 连出去的总容量比较但这样做在特殊图里可能出问题如果 SS 连出去的某条边容量很大某条边容量很小总流量相同也不能保证每条边都满了因为流量可能被错误地分配。正确做法是遍历所有从 SS 出发的边检查每条边的剩余容量是否为 0。只有全部为 0才说明所有多余的流入都被送走了可行流才真正存在。5.2 第二次最大流之前必须清场第一次跑完之后残量网络里还留着 SS、TT 以及它们连出去的边。如果不清掉这些边第二次从 s 到 t 跑最大流时增广路可能绕道 SS 或 TT产生完全不存在的流量答案直接虚高。清理的标准做法有两种一种是在建图时记录所有涉及 SS、TT 的边的下标清场时把这些边手动删掉另一种是给这些边打一个标记在 BFS 时直接跳过。我倾向第一种因为删除边的逻辑更直观不容易漏。同时别忘了删掉 t→s 那条 INF 边。如果它还在第二次最大流又可以从 t 直接回流到 s等于凭空多了一条无限容量的通道结果必错。5.3 INF 的大小和溢出上下界流里的 INF 要足够大至少要大于整个网络所有下界之和因为它要充当 t→s 的“总回流通道”还要充当拆点边的上限。很多题解里喜欢写 1e9但如果所有边的下界都是 1e9 级别总和可能超过 int 范围。我自己的习惯是用 long long 存流量INF 取 1e18 再在和值累加时小心一点。严谨的做法是先遍历一遍所有边算出下界总和让 INF 等于这个总和加 1。至少能保证不会因为 INF 不够大而漏解。5.4 无向边的成对弧问题Dinic 里 addEdge 会同时建一条反向边反向边的容量初始为 0用来支持流量回退。如果一条无向边被拆成两条有向边而每条都分别调用 addEdge那么这两条有向边会各自拥有一对弧可能导致“正向流 1、反向回退 1”的假象流量相当于一条路被修了又拆最后状态却不合法。物理上无向边只能选一次。所以我强烈建议用“中间点”的方式把无向边变成一个节点加两条容量为 1 的有向边这样流量只会从一端进入、从另一端出去不会出现同一方向来回收割的情况。这个模型虽然多 O(m) 个点但正确性高很多。5.5 多组数据的打扫战场CF 这类题库经常是多组测试数据而我的 Dinic 模板用的是全局 vector如果不注意清理上一组的残量边会一直累积导致各种奇怪 WA。建图前要把边表、head、level 全部重置如果为了方便而保留了节点总数还要特别注意节点编号是否超出上一组的范围。一个实用小技巧把整个 Dinic 结构体写成一个类每一组数据重新 new 一个实例天然避免串数据。代码风格稍微“重”一点但比 DEBUG 一个小时的边界问题划算得多。6. 完整解题流程与复杂度参考6.1 从输入到输出的七个步骤第 1 步读入点数 n 和边信息区分哪些边是必选树边、哪些是可选边第 2 步用并查集或拓扑删叶法找出基环树的唯一环记录环上的节点第 3 步拆点构建网络流图把每个度数限制写成拆点边的上下界第 4 步把所有可选边、必选边、环边统一转成有向流边注意无向边用中间点法处理第 5 步加入 t→s INF 边建超级源 SS、超级汇 TT按收支差 d[u] 连边第 6 步跑第一次 SS → TT 最大流检查 SS 出边是否满流不满则无解第 7 步如需最大化清场后跑第二次 s→t 最大流最终答案 flowA flowB。这个流程几乎可以当模板用唯一需要根据题面微调的是“点数上限怎么拆”“环找到之后怎么往网络里塞”。6.2 复杂度与一个改进思路基环树相关操作都是 O(n) 的瓶颈在 Dinic 上。一般来说拆点后节点数在 2n O(m) 量级边数在 O(n) 量级Dinic 的最坏复杂度是 O(V²E)但实际跑稀疏网络时远到不了这个界通常能在一秒左右完成。如果遇到更大的数据范围可以考虑用容量缩放 BFS 或者对基环树的环部分做额外预处理把第一次最大流的规模压小。不过竞赛里这种题的数据范围一般不会设置得太极限因为“建上下界网络 两次 Dinic”本身就是考察点数据规模给太大反而偏离了重点。我个人的改进经验是环上的节点数量一般很小可以把环边从网络里单独提出先枚举环的几种流量取值把问题拆成若干个纯树上的可行流判定。这样可以让每次最大流的图变小但代码复杂度会明显上升。除非时间卡得很紧否则直接整体建模更划算。最后再分享一个小技巧做这类“树上选边 度数约束”的网络流题可以先在纸上把基环树的环画出来标上每个点的需求区间你会发现环上的可调范围就是从“所有树边下界总和”到“所有树边上界总和”之间的那一段。想通了这一点再看有源汇有上下界的最大流模板就会觉得每一步都顺理成章。这道题真正难的地方不是 Dinic 本身而是你要意识到一个环的循环自由度正是上下界流模型最擅长处理的东西。