OI-wiki 上下界网络流全解从无源汇可行流到有源汇最大流与最小流【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki上下界网络流是网络流建模的重要扩展普通网络流只给每条边设置流量上界容量而上下界网络流同时为每条边规定流量下界与上界要求流量必须落在 $[b(u,v),, c(u,v)]$ 区间内。它常用于刻画至少流多少、至多流多少的现实约束例如剧情触发次数下限、资源供给下限等场景。本文以 OI-wiki 的 上下界网络流文档 为主体结合仓库内完整可运行的参考实现与测试数据系统讲解无源汇可行流、有源汇可行流、上下界最大流与上下界最小流四类问题的建模方法与代码细节。读完本文你将掌握上下界网络流的统一建图框架附加源汇点 附加边 残量网络二次增广并能独立写出可提交的模板代码。前置知识上下界网络流建立在最大流算法之上。在开始之前请先阅读 最大流并确保熟练掌握至少一种最大流算法如 Dinic、ISAP、预流推进理解以下核心概念容量限制普通网络中 $0 \leq f(u,v) \leq c(u,v)$流守恒性除源点 $s$ 与汇点 $t$ 外任意结点的净流量为 $0$残量网络$G_f$由所有剩余容量 $c_f(u,v)c(u,v)-f(u,v)0$ 的边构成的网络是上下界网络流二次增广的舞台增广与退流最大流算法通过反复寻找增广路增加流量反向边则用于反悔抵消这一机制在后续删边与退流操作中同样关键。其余基本概念网络、流、割可参考 网络流简介。概述上下界网络流是什么上下界网络流的本质是给流量网络的每条边同时设置流量上界$c(u,v)$ 与流量下界$b(u,v)$。一种可行流必须满足$$ b(u,v) \leq f(u,v) \leq c(u,v) $$同时除了源点和汇点之外其余点都必须满足流量平衡流入量等于流出量。注意普通最大流可以看作所有边下界为 $0$ 的上下界网络流特例。根据题目要求的不同我们可以用上下界网络流解决四类问题问题类型询问内容核心手段无源汇上下界可行流是否存在满足边上下界与全点平衡的流附加源/汇点 附加边判满流有源汇上下界可行流是否存在满足边上下界、除源汇外全平衡的流加 $T \to S$ 无穷边转化为无源汇问题有源汇上下界最大流存在的前提下源到汇的最大流量残量网络上再跑一次 $S \to T$ 最大流有源汇上下界最小流存在的前提下源到汇的最小流量残量网络上跑 $T \to S$ 最大流退流无源汇上下界可行流问题定义给定无源汇流量网络 $G$即不区分源点汇点所有点都要求流量平衡询问是否存在一种标定每条边流量的方式使得每条边的流量同时满足上下界且每一个点的流量都平衡。核心思想初始流 附加边调整这是所有上下界网络流问题的地基其建图思路分为三步。第一步——预流下界构造初始流。不妨假设每条边已经流了 $b(u,v)$ 的流量称其为初始流同时在新建的图中加入 $u$ 连向 $v$、容量为 $c(u,v)-b(u,v)$ 的剩余容量边。接下来的任务是在新图上做调整。第二步——计算每个点的失衡量 $M$。由于最大流天然满足流量平衡等价于下界为 $0$ 的上下界流但上面构造的初始流很可能不满足流量平衡。对每个点记$$ M \text{初始流入流量} - \text{初始流出流量} $$分三种情况处理$M 0$该点流量平衡不需要附加边$M 0$该点入流量过大需要新建附加源点$S$并连一条 $S \to u$、容量为 $M$ 的附加边用来抽出多余的入流$M 0$该点出流量过大需要新建附加汇点$T$并连一条 $u \to T$、容量为 $-M$ 的附加边用来补足欠缺的出流。第三步——跑最大流并判满流。在建图完毕后跑一遍 $S$ 到 $T$ 的最大流。判断规则是若 $S$ 连出去的所有附加边全部满流则原网络存在可行流否则不存在可行流。这里的判定逻辑是附加边满流意味着额外流入的 $M$ 单位的流恰好被最大流通过剩余容量边送走或送来这样加上附加流之后原图中的每个点都能恢复流量平衡。注意只有原图加上附加流之后才满足原图中的流量平衡条件——这正是附加边满流 ⇔ 可行流存在的充要性所在。参考实现bound_1.cpp 逐行解析仓库中的 docs/graph/code/flow/bound/bound_1.cpp 是 Luogu P14578【模板】无源汇上下界可行流的完整 AC 代码采用 Dinic 算法作为最大流内核。其中与上下界建图直接相关的部分如下constexpr int MAXN 3e4 10; constexpr int INF 1e9 10; int n, m, s 0, t; int ecnt 1, head[MAXN], dep[MAXN], now[MAXN], l[MAXN], d[MAXN], id[MAXN]; // 读入并建图 for (int i 1; i m; i) { int u, v, r; cin u v l[i] r; add_edge(u, v, r - l[i]); // 加入容量为 上界-下界 的剩余容量边 add_edge(v, u, 0); // 反向边 id[i] ecnt; // 记录正向边的编号输出答案时使用 d[v] l[i]; // v 的流入下界累加 d[u] - l[i]; // u 的流出下界累加 }这段代码与上文建图框架的对应关系非常清晰数组l[i]保存每条边流量的下界 $b(u,v)$d[i]累计每个点的失衡量 $M$d[v] l[i]表示下界流流入 $v$d[u] - l[i]表示下界流从 $u$ 流出最终d[i] 0对应 $M0$入流过大d[i] 0对应 $M0$出流过大id[i] ecnt在加入正向边后立即记录其编号因为最终需要输出每条边上的真实流量随后连接附加源汇点并统计附加源点总出容量long long sum 0; for (int i 1; i n; i) { if (d[i] 0) { add_edge(s, i, d[i]); // 附加源点 S 0 连向失衡点 add_edge(i, s, 0); sum d[i]; // S 连出去的总容量 } else if (d[i] 0) { add_edge(i, t, -d[i]); // 失衡点连向附加汇点 T n1 add_edge(t, i, 0); } }注意这里s 0, t n 1即附加源点复用编号 $0$、附加汇点复用编号 $n1$与普通最大流模板的写法完全兼容。最后跑 Dinic 并判定long long ans 0; while (bfs()) ans dfs(s, INF); if (ans sum) { cout No\n; return 0; } cout Yes\n; for (int i 1; i m; i) cout e[id[i]].w l[i] \n;最大流值ans必须等于附加源点总出容量sum即全部附加边满流否则输出No输出每条边真实流量时用残量边剩余容量 下界恢复e[id[i]].w l[i]这正是初始流 $b$ 附加流的叠加结果。用仓库测试数据验证仓库在 docs/graph/examples/flow/bound/bound_1.in 提供了一组测试数据$n6,m7$形如u v l r6 7 1 2 3 5 2 3 3 4 3 4 5 6 4 1 1 5 4 5 0 3 6 3 0 1 4 6 0 1对应的标准输出 bound_1.ans 为Yes 4 4 5 4 0 1 1逐条验证边 $1\to2$ 流量 $4\in[3,5]$$2\to3$ 流量 $4\in[3,4]$$3\to4$ 流量 $5\in[5,6]$$4\to1$ 流量 $4\in[1,5]$$4\to5$ 流量 $0$$6\to3$ 流量 $1$$4\to6$ 流量 $1$。每个点的流入流出均相等如点 $3$流入 $415$流出 $5$点 $4$流入 $5$流出 $4015$完整满足下界约束与流量平衡。这份测试数据与答案可直接用于验证你自己的实现。有源汇上下界可行流问题定义给定有源汇流量网络 $G$询问是否存在一种标定每条边流量的方式使得每条边流量满足上下界且除了源点 $S$ 和汇点 $T$ 外每一个点流量平衡。转化技巧加入 $T \to S$ 无穷边假设源点为 $S$、汇点为 $T$。核心转化只有一步加入一条 $T \to S$、上界为 $\infty$、下界为 $0$ 的附加边就把有源汇问题转化成了无源汇上下界可行流问题。其正确性在于无源汇模型要求所有点流量平衡这等价于强制源点 $S$ 的净流出等于汇点 $T$ 的净流入——恰好对应源汇之间的流量。而 $T\to S$ 这条反向附加边恰好承接了这段差额。若有解则$S$ 到 $T$ 的可行流流量等于 $T$ 到 $S$ 的附加边上的流量。因此在求解结束后读出这条附加边上的流量就是原问题源到汇的可行流流量。有源汇上下界最大流问题定义给定有源汇流量网络 $G$询问是否存在满足边上下界、除源汇外全点平衡的流如果存在进一步询问满足标定条件下的最大流量。算法流程先求可行流再在残量网络上增广求解分三个阶段求任意可行流。先按上文有源汇可行流的方法找到网络上的任意一个可行流。如果找不到解直接结束删去所有附加边包括 $T\to S$ 的无穷边以及与 $S$、$T$ 相连的边得到原网络的残量网络在残量网络上再跑一次 $S \to T$ 的最大流将可行流流量 最大流流量相加即为答案。第二阶段的意义是可行流已经把每条边垫到了下界以上残量网络中剩余的调整空间$c_f$才是可以继续榨取流量余地。在残量网络上增广既能保证不破坏下界约束不会把流量压回下界以下又能把流量推向最大。⚠️ 一个非常易错的问题$S$ 到 $T$ 的最大流必须直接在跑完有源汇上下界可行流之后的残量网络上跑。千万不可以在原来的流量网络上跑。这是因为原网络的边没有下界信息直接在原网络上跑最大流得到的是普通最大流完全无法保证流量不小于下界 $b(u,v)$结果必然错误。正确做法必须复用可行流阶段留下的残量网络——其中每条边的剩余容量 $c_f(u,v)c(u,v)-f(u,v)$ 已经蕴含了下界约束因为 $f(u,v)\geq b(u,v)$ 已被满足。有源汇上下界最小流问题定义给定有源汇流量网络 $G$询问是否存在满足边上下界、除源汇外全点平衡的流如果存在询问满足标定条件下的最小流量。算法流程找到可行流后把多余的流退掉与最大流对称最小流的思想是将残量网络中不需要的流退掉求任意可行流。同样先找到网络上的任意一个可行流找不到就直接结束删去所有附加边得到原网络的残量网络在残量网络上跑一次 $T \to S$ 的最大流将可行流流量 $-$ 最大流流量即为答案。由于 $T\to S$ 方向的最大流相当于从 $T$ 到 $S$ 送流量在反向图上等效于把 $S\to T$ 方向上可退掉的流量全部退回从而在不突破下界的前提下把总流量压到最小。例题AHOI 2014 支线剧情原文档给出了一个典型应用——AHOI 2014「支线剧情」LibreOJ 2226其建图方式展示了上下界与费用流结合的实际套路对于每条 $x \to y$、花费 $v$ 的剧情边设上界为 $\infty$下界为 $1$每条剧情必须且至少触发一次对于每个点向汇点 $T$ 连边权为 $c$、上界 $\infty$、下界为 $1$的边保证每个点都能结束一条支线源点 $S$ 为 $1$ 号节点跑一次上下界带源汇最小费用可行流即可得到答案。由于最小费用可行流的求解思路与最小可行流高度类似都是先找可行流、再在残量网络上用最短路增广/退流原文档对此不再展开理解上文中最小流的框架后只需将最大流内核替换为最小费用最大流可参考 最小费用最大流 中的 SSP 算法即可实现。小结与常见易错点把四类问题串起来看上下界网络流其实只有一套方法论预流下界每条边先流满下界 $b(u,v)$记录失衡量 $M$附加源汇$M0$ 连 $S\to u$$M0$ 连 $u\to T$判定可行$S\to T$ 最大流满流 ⇔ 可行流存在有源汇转化加 $T\to S$ 无穷边把有源汇化为无源汇最大/最小流删去附加边后分别在残量网络上跑 $S\to T$ 或 $T\to S$ 的最大流与可行流流量相加或相减。常见易错点归纳如下易错点正确做法附加边满流判定必须检查附加源点 $S$ 连出的所有边是否全部满流ans sum而非只看最大流是否够大输出真实流量真实流量 残量剩余 下界即e[id[i]].w l[i]最大流的二次增广网络只能在删去附加边后的残量网络上跑不能在原网络或原最大流网络上跑最小流的退流方向用 $T \to S$ 的最大流来退流结果做减法而非加法附加边编号记录用id[i]在加正向边后立即记录编号避免输出时找错边如需进一步深入可继续阅读仓库内相关的 最大流、最小割、最小费用最大流 文档以及可运行模板代码 bound_1.cpp 和配套测试数据 bound_1.in、bound_1.ans。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考