← 线性规划网络流 · 最大流、最小割与建模归约 / 建模与归约：把问题翻译成网络流 待审核 10 / 13
建模与归约 · 拆点 · 路径覆盖

建模与归约：把问题翻译成网络流

前面各页解决的是「给定流网络，怎么求最大流 / 最小割 / 匹配」。但真实问题极少直接长成一张流网络的样子——它可能是「把若干工人分派到若干岗位」「选一批盈利项目」「用最少巡逻路线覆盖所有路口」。本页讲的是建模 (modeling) 与归约 (reduction)：如何把一个看似无关的问题，翻译成一张流网络，使它的最大流 / 最小割恰好是原问题的答案。归约的价值在于：一旦翻译成功，就能直接套用前面各页的成熟算法，无需为每个新问题重新发明求解器。

每个套路都按同一三段式拆解——原问题是什么 → 怎么建图（节点 / 边 / 容量怎么定）→ 答案怎么读（求出的最大流 / 最小割如何翻译回原问题的解）。本页涵盖五个经典模型：多源多汇 · 点容量（拆点）· DAG 最小路径覆盖 · 最大权闭合子图 · 密度子图（简述），末尾给出一张归约速查表。

1 · 多源多汇：超级源与超级汇

标准最大流只有一个源 s 与一个汇 t。但很多调配问题有多个供给点（几座工厂、几个发电厂）与多个需求点（几座仓库、几个城区）。这类「多源多汇最大流」不必另写算法，一个标准技巧即可归约回单源单汇。

原问题 源集合 {s₁, s₂, …}、汇集合 {t₁, t₂, …}，问从所有源到所有汇总共能输送多少流量。

怎么建图 新增一个超级源 super source S 与超级汇 super sink T。对每个原源 sis_i 连一条 S→siS \to s_i；对每个原汇 tjt_j 连一条 tj→Tt_j \to T。这些新边的容量：若源 / 汇本身无产出 / 吸纳上限，取 ∞\infty（实现上取一个大于总容量的数即可）；若 sis_i 最多产出 pip_i、tjt_j 最多吸纳 qjq_j，则把这个上限写成对应新边的容量。

答案怎么读 在新图上求 S→TS \to T 的最大流，其值就是多源多汇的最大总流量；每条原边的流量即各自的实际调配量。

为什么对？ 超级源 S 是一个纯「分发器」：它没有容量约束（或仅有产出上限），把任意流量经 S→siS \to s_i 派给各源，等价于「各源自由产出」。超级汇 T 对称地汇集各汇的流入。因此新图的任一 S→TS\to T 流，去掉 S、T 后一一对应原图的一个合法多源多汇流，流值相等——两个问题的可行解集同构，最优值自然相等。

下面是一张具体的两源两汇网：源 s1（产出上限 5）、s2（上限 4），汇 t1（吸纳上限 4）、t2（上限 3），中转点 m。加上超级源 S、超级汇 T 后求最大流，结果为 7。单步看流是怎么充满这张网的。

边界： 当源 / 汇带产出 / 吸纳上限时，这恰好就是「把上限建成 S→siS\to s_i / tj→Tt_j\to T 边的容量」。若进一步要求每条边或每个点还有下界（必须至少流多少），那是更强的上下界可行流问题，见 上下界网络流。

2 · 点容量：拆点 (vertex splitting)

标准流网络只给边设容量，点是「无限大的中转站」。但现实里点也常有通过上限——一个机场每小时最多放行多少架次、一个路由器每秒最多转发多少包、一条隧道最多通过多少车。把「点容量」翻译成「边容量」的标准手法是拆点 (splitting)。

原问题 点 v 有一个通过上限 c(v)：经过 v 的总流量不得超过 c(v)。

怎么建图 把每个有上限的点 v 拆成两个点 v_in 与 v_out，中间连一条 vin→voutv_in \to v_out，容量正是点容量 c(v)。原本进入 v 的边全部改接到 v_in；原本从 v 发出的边全部改从 v_out 发出。

答案怎么读 在拆点后的图上跑标准最大流即可。所有流量进出 v 都必经那条 vin→voutv_in \to v_out 边，于是「经过 v 的流量 ≤ c(v)」被边容量自动强制。最大流值就是原问题的答案。

为什么对？拆点后，v_in 是 v 全部流入的唯一汇聚口、v_out 是全部流出的唯一发出口，二者之间只有一条 c(v) 容量的桥。任何穿过 v 的流都必须挤过这座桥，因此「通过 v 的总量」与「桥上的流量」恒等，点容量约束等价转化为这条边的容量约束。这个技巧也是 二分图最大匹配 里「每个工人只能接一个任务」的实现方式——把工人拆成入 / 出两点、中间容量 1。

最小的演示：s→v→ts \to v \to t，两侧边容量都是 5，但点 v 的通过上限只有 2。拆成 vin→voutv_in \to v_out（容量 2）后，无论两侧多宽，最大流都被那条桥卡在 2。

3 · DAG 最小路径覆盖

给一个有向无环图 DAG，要用最少条顶点不相交的简单路径，覆盖图中所有点（每个点恰好属于一条路径）。这是「用最少巡逻员 / 最少模具，各自走一条不回头的链，把所有站点 / 工序都做掉」一类调度问题的抽象。它出人意料地归约成二分图最大匹配（见 二分图最大匹配）。

原问题 DAG 有 n 个点，求覆盖全部点的最小顶点不相交路径数（单个点也算一条长度为 0 的路径）。

怎么建图 建一个二分图：把每个点 v 拆成出点 v_out（放左部）与入点 v_in（放右部）。DAG 里每条边 u→vu \to v 在二分图里变成一条 u_out — v_in。再对这个二分图求最大匹配。

答案怎么读 最小路径覆盖数 = 点数 n − 二分图最大匹配数 M。每条匹配边 u_out — v_in 表示「在覆盖里让 u 紧接 v」，把这些「衔接」串起来就还原出各条路径。

为什么是 n−Mn - M? 一开始把每个点各算一条路径，共 n 条。每选用一条匹配边 u_out — v_in，等于把 v 这条路径接到 u 路径的尾巴上，路径总数减一。匹配的「不相交」恰好保证：每个点至多有一个后继（出点最多匹配一次）、至多有一个前驱（入点最多匹配一次），于是衔接出来的一定是若干条不分叉、不相交的链。匹配越大、合并越多、路径越少——所以最大匹配 M 对应最少路径数 n−Mn - M。

具体例子：5 点 DAG，边为 1→2{1\to 2}、1→3{1\to 3}、2→4{2\to 4}、3→4{3\to 4}、4→5{4\to 5}。把它拆成左部出点 {1ₒ…5ₒ}、右部入点 {1ᵢ…5ᵢ}，用单位容量建成匹配网 s→各vo→各vi→ts \to 各 vₒ \to 各 v_i \to t，跑最大流读出匹配。下面这张网的最大匹配 = 3，故最小路径覆盖 = 5−3={5 - 3 =} 2。

读回路径： 跑满后匹配边为 1→2{1\to 2}、2→4{2\to 4}、4→5{4\to 5}，衔接成一条长链 1 → 2 → 4 → 5；点 3 没能接进任何链（它的后继 4 已被 2 占用），自成一条长度 0 的路径 3。两条路径恰好覆盖全部 5 点。注意：此模型要求路径顶点不相交；若允许相交（最小可重叠路径覆盖），需先对 DAG 求传递闭包再套同一套匹配。

4 · 最大权闭合子图(project selection)

前三个模型都是「最大流」型（配对 / 调配）。这一个换成最小割型，是最小割最经典、也最反直觉的应用。在一个有向图上，每个点有一个权值（可正可负），要选一个点集 C，满足闭合性：只要选了 u，就必须把 u 指向的所有后继也选进来；在此前提下让所选点的权值之和最大。这就是「最大收益项目选择 maximum weight closure / project selection」：做一个项目能赚钱（正权），但它依赖某些要花钱的前置投入（负权），选了项目就得为它的依赖买单。

原问题 有向依赖图，点权 w(v)（项目正、设备 / 成本负），依赖边 u→vu \to v 表示「选 u 必选 v」。求一个闭合子图，使总权 ∑w(v)\sum w(v) 最大。

怎么建图 加源 s、汇 t。其一：对每个正权点 v，连 s→vs \to v，容量 = w(v)；其二：对每个负权点 v，连 v→tv \to t，容量 = |w(v)|；其三：每条原依赖边 u→vu \to v 连成 u→vu \to v，容量 = ∞\infty（永不被割断）。

答案怎么读 求 s−ts-t 最小割。最大权 = 正权总和 − 最小割容量。割的源侧 S（去掉 s）就是要选的项目集合 C。

为什么对？把「点 v 落在源侧 S」解释为「选 v」。依赖边容量 ∞\infty 意味着割绝不会切断 u→vu \to v：若 u∈Su \in S 而 v∉Sv \notin S 就会割到一条无穷边，代价无穷大——这正好强制了闭合性（选 u 必选 v）。在闭合的前提下，一个割的有限代价 =「没选的正权点」失去的 s→vs\to v 边（放弃的收益）+「选了的负权点」付出的 v→tv\to t 边（承担的成本）。于是 正权总和−割=选中的正权−选中的负成本=所选子图的净权正权总和 - 割 = 选中的正权 - 选中的负成本 = 所选子图的净权，最小化割即最大化净权。

具体例子：两个项目 p1（收益 +3）、p2（收益 +2）；两项前置投入 e1（成本 −4）、e2（成本 −1）。依赖：p1 需要 e1 和 e2,p2 只需要 e2。正权总和 = 3 + 2 = 5。下面在自建网上跑出最小割。

读这张图： 最优选择是 {p2, e2}——做 p2(+2)、为它买 e2(−1)，净赚 1。p1 虽收益 +3，但它必须连带 e1(−4)与 e2(−1)，做了反而净亏，故割把 p1 留在汇侧（放弃）。正权总和 5 − 最小割 4 = 1，与逐项核算一致。最小割与最大流的完整对应见 最小割。

5 · 再举一例：最大密度子图（简述）

还有许多问题归约到最小割，这里只点一例。最大密度子图 (densest subgraph)：在无向图里找一个点集 U，使密度 (U 内部边数) / |U| 最大。它可以二分一个密度阈值 g，把「是否存在密度 ≥ g 的子图」化成一个参数化的最小割 / 最大权闭合判定——把每条边看成「收益 1、但依赖它两个端点」的项目，端点带 −g-g 的成本，再对 g 做参数搜索。它与上一节的闭合模型同属「最小割 = 取舍」家族。这类「连续参数 + 最小割判定」的题，统一视角要到 LP / 对偶才看得透。

6 · 归约速查表

把本页的归约浓缩成一张表——遇到新题先对照「建图要点」，确认它属于「最大流」型还是「最小割」型。

原问题 建图要点 答案
多源多汇 超级源 $S\to 各源$（cap=∞ 或产出上限）、各汇 $\to T$（cap=∞ 或吸纳上限） max-flow(S,T)
点容量 点 v 拆成 $v_in\to v_out$,cap = 点容量；入边接 v_in、出边从 v_out max-flow
DAG 最小路径覆盖 每点拆出点 / 入点，原边 $u\to v$ ⟹ $uₒ—v_i$，求二分图最大匹配 M $n - M$
最大权闭合子图(project selection) $s\to$正权（cap=权）、负权 $\to t$（cap = 权的绝对值）、依赖边 $u\to v$(cap=∞) $\sum 正权 - \min -cut$
最大密度子图 二分密度 g；边为收益项目、端点带 $-g$ 成本，转最大权闭合 / 最小割判定 参数搜索 + min-cut

建模的两个母题。 绝大多数网络流应用落在两类之一：

「最大流」型——配对 / 调配 / 可行：把「供给 → 需求」串成一条条增广路，问能输送 / 配对多少。多源多汇、点容量、二分图匹配、路径覆盖都属此类。

「最小割」型——取舍 / 分割 / project selection：把每个对象「归源侧还是汇侧」当作一个二选一决策，用割的代价编码「选错要付的代价」，最小割即最优取舍。最大权闭合、图像分割、密度子图都属此类。

拿到一道题，先判断它在求「能流多少」还是在做「怎么分两边」，基本就锁定了归约方向。带下界约束的可行 / 最小流见 上下界网络流；把最大流 / 最小割统一进 LP 与对偶的视角，见 LP 对偶。

注 · 归约还顺带丢掉了回溯，这一层收益容易被忽略。

上面每个套路的原问题都可以用「贪心加回溯」硬做：任务分派试着配、冲突就退回换人；项目取舍枚举 $2^n$ 个子集。归约成流之后，这些搜索变成了增广，而增广次数不随争抢的激烈程度变化。撤销与回溯 那页把两条路线放在同一批用例上量化对照过，其中也有回溯反而更省的反例。