企业官网建设流程全解析

最小割问题完全指南：最大流最小割定理、建图模型与 OI 实战（OI-wiki）

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

最小割（Minimum Cut）是网络流理论中与最大流地位对等的核心概念：给定一个有源汇点的网络 $G=(V,E)$，最小割是在所有把源点 $s$ 与汇点 $t$ 分开的点集划分中，找到割容量最小的一种。由于最大流最小割定理保证任意网络上的最大流数值恒等于最小割容量，最小割在 OI/ICPC 竞赛中不仅是独立的图论题型，更是一类极其重要的建模工具——"二者选其一"的决策问题、最大权值闭合图等经典模型，最终都归结为一次最小割计算。阅读本文后，你将掌握割与割容量的严格定义、最大流最小割定理的证明脉络、基于 Dinic 求最小割及输出割方案的完整代码，以及两大经典建图模型的推导过程。

本文主体基于仓库 最小割文档，并补充 网络流简介 与 最大流文档 中的定义与定理证明细节，帮助读者建立从概念到代码、再到建模的完整链条。

一、基本概念：割、割的容量与最小割

1.1 割（Cut）

对于一个网络流图 $G=(V,E)$，其割的定义为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。

在 网络流简介 中，这一概念以更形式化的方式给出：若 ${S,T}$ 是 $V$ 的划分（即 $S\cup T=V$ 且 $S\cap T=\varnothing$），且满足 $s\in S,t\in T$，则称 ${S,T}$ 是 $G$ 的一个 $s$-$t$ 割（cut）。注意割的划分对象是点集，而非边集——"割"这个名字容易让人误以为要删边，但数学定义上是把顶点分成两组。

1.2 割的容量（Capacity of Cut）

定义割 $(S,T)$ 的容量 $c(S,T)$ 为所有从 $S$ 到 $T$ 的边的容量之和：

$$ c(S,T)=\sum_{u\in S,v\in T}c(u,v) $$

也可以简写为 $c(s,t)$ 表示 $c(S,T)$。关键点在于：

• 只统计从 $S$ 指向 $T$的有向边，反向边（$T$ 到 $S$）不贡献容量；
• 容量是边权val（容量）而非流量，与当前流 $f$ 无关。

1.3 最小割（Minimum Cut）

最小割就是求得一个割 $(S,T)$，使得割的容量 $c(S,T)$ 最小。

需要与另一类"最小割"区分：本文讨论的是有固定源汇点的 $s$-$t$ 最小割；若要求无向图中任意两点间所有割的最小值，则属于全局最小割问题，可用 Stoer-Wagner 算法 在 $O(n^3)$ 内解决。二者的区分在建模时很重要：全局最小割类问题（如求断开图所需删除的最小边权和）不应套用本页的源汇建模。

二、最大流最小割定理：最小割可计算的根基

2.1 定理内容

最大流最小割定理（The Maxflow-Mincut Theorem）指出：对于任意网络 $G=(V,E)$，其上的最大流 $f$ 和最小割 ${S,T}$ 总是满足

$$ |f| = ||S,T|| $$

即最大流的数值等于最小割的容量。这正是 最大流文档 中最大流最小割定理一节的结论，也是本页全部代码与建模技巧的理论支柱：想求最小割，跑一遍最大流即可。

2.2 定理证明的两个阶段

从 最大流文档 的证明看，定理的严格证明分两步。

第一步：证明任意流不超过任意割（引理）。对任意流 $f$ 和任意割 ${S,T}$，恒有 $|f| \leq ||S,T||$。推导核心是反复使用流守恒性展开 $s$ 的净流量：

$$ |f| = f(s) = \sum_{u \in S} f(u) = \sum_{u\in S}\sum_{v\in T} f(u,v) - \sum_{u\in S}\sum_{v\in T} f(v,u) \leq \sum_{u \in S} \sum_{v \in T} c(u,v) = ||S,T|| $$

取等需要同时满足两个条件：${(u,v)\mid u\in T, v\in S}$（从 $T$ 到 $S$）的所有边均空流，且 ${(u,v)\mid u\in S, v\in T}$ 的所有边均满流。

第二步：证明存在流与割取等。假设某一轮增广后得到流 $f$，使残量网络 $G_f$ 上不存在从 $s$ 到 $t$ 的增广路。记 $S$ 为从 $s$ 出发在 $G_f$ 上可达的点集，$T=V\setminus S$。则 ${S,T}$ 是 $G_f$ 的一个割且其残量容量为 $0$，逐边讨论可得：

• 对 $(u,v)\in E$：$c_f(u,v)=c(u,v)-f(u,v)=0$，即从 $S$ 到 $T$ 的边全部满流；
• 对 $(v,u)\in E$：$f(v,u)=0$，即从 $T$ 到 $S$ 的边全部空流。

因此该 $f$ 满足引理的取等条件，$f$ 是最大流，${S,T}$ 是最小割，定理得证。

2.3 相关推论

• Kőnig 定理是最大流最小割定理的特殊情形；
• 二者都与线性规划中的对偶理论有关（详见 线性规划 页面中网络流对偶的讨论）；
• 在 拟阵理论 中同样能看到"对偶"思想的身影。

三、求最小割：基于 Dinic 的完整实现

3.1 思路：把最小割变成最大流

由最大流最小割定理，直接求一次最大流即得到最小割容量。竞赛实践中主流选择是 Dinic 算法（BFS 分层 + DFS 多路增广 + 当前弧优化），其最坏时间复杂度为 $O(|V|^2|E|)$，实际表现远好于理论上界。下面是 最小割文档 给出的完整参考代码：

#include <algorithm> #include <cstdio> #include <cstring> #include <queue> constexpr int N = 1e4 + 5, M = 2e5 + 5; int n, m, s, t, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) q.push(v), dep[v] = dep[u] + 1; } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) val[i] -= x, val[i ^ 1] += x, ans += x; } } if (ans < flow) dep[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, 1 << 30))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } printf("%d\n", dinic(s, t)); return 0; }

实现细节值得说明：

• 边的编号技巧：tot从 1 开始，addedge保证正向边与反向边编号相邻，因此i ^ 1恒为该边的反向边（反向边初始容量为 0，用于退流）——这正是 最大流文档 中介绍的链式前向星惯用技巧；
• bfs 分层：每次增广前用 BFS 建立层次图，只允许流量从第 $d$ 层流向第 $d+1$ 层；
• dfs 多路增广 + 当前弧：cur[u]记录 $u$ 当前还未增广到极限的出边指针。需要强调的是，当前弧优化是保证 Dinic 复杂度正确性的组成部分，而"多路增广"只是常数优化，两者不应并列称为"两种优化"（这一常见误区在 最大流文档 中有专门澄清）；
• dep[u] = -1是一种剪枝：若 $u$ 本轮无法再送出流量，直接将其从层次图中剔除，避免后续无效访问。

3.2 输出割方案：从源点 DFS 残量网络

只求出容量往往不够，很多题目要求输出割的具体方案（即 $S$ 集合包含哪些点）。依据定理证明第二步的构造方法：最大流跑完后，从源点 $s$ 开始 DFS，只走残量大于 $0$ 的边，能到达的点全部属于 $S$ 集合，其余点属于 $T$ 集合。代码如下：

void dfs(int u) { vis[u] = 1; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (!vis[v] && val[i]) dfs(v); } }

跑完dinic(s, t)后调用dfs(s)，则vis为真的点构成最小割的 $S$ 侧。其正确性来自定理证明本身：增广终止后 $S$ 内点沿残量边无法到达 $T$ 内点，而跨越 $S/T$ 的原图边恰好满流，边权和即最小割容量。

3.3 附加技巧：最小化割边数量

原文档还给出一个高频技巧——在最小割前提下最小化割边数量：

1. 先求出原图的最小割（跑一遍最大流）；
2. 把没有满流的边容量改成 $\infty$，把满流的边容量改成 $1$；
3. 重新跑一遍最小割，得到的数值即为最小割边数量。

原理是：第一遍求解后满流的边才是"候选割边"，第二遍建图让每条候选割边代价为 1，于是最小化割容量的过程等价于最小化被割断的边数；$\infty$ 保证非满流边永远不进入最小割。若无"最小割为前提"的要求，则直接把所有边的容量设为 $1$，求一遍最小割即可得到最少割边数。

该技巧的典型应用是「USACO 4.4」Pollutant Control（见文末习题），它要求输出最小的污染控制费用，而在费用最小的方案中再最小化被切断的管道条数。

四、问题模型 1：二者选其一（决策式建模）

4.1 问题描述

有 $n$ 个物品和两个集合 $A,B$。每个物品必须且只能属于一个集合：

• 物品 $i$ 没有放入 $A$ 集合会花费 $a_i$（即放入 $B$ 的代价）；
• 物品 $i$ 没有放入 $B$ 集合会花费 $b_i$（即放入 $A$ 的代价）；
• 另有若干形如 $(u_i,v_i,w_i)$ 的限制：如果 $u_i$ 和 $v_i$ 同时不在一个集合，会额外花费 $w_i$。

求最小总代价。

4.2 建图方法

这是经典的二者选其一最小割模型：

1. 对每个集合建立超级源点 $s$ 和超级汇点 $t$；
2. 第 $i$ 个点由 $s$ 连一条容量为 $a_i$ 的边，向 $t$ 连一条容量为 $b_i$ 的边；
3. 对每个限制条件 $(u,v,w)$，在 $u,v$ 之间连容量为 $w$ 的双向边；
4. 答案 = 最大流（= 最小割容量）。

4.3 割的意义：为什么最小割就是最小花费

理解的关键在于割与"选择"的一一对应：

• 当源点和汇点不相连时，每个点必然选择其中一个集合；
• 若割断了连向 $s$ 的边，表示该点不放入 $A$ 集合，付出 $a_i$ 的代价；
• 若割断了连向 $t$ 的边，表示该点不放入 $B$ 集合，付出 $b_i$ 的代价；
• 若割断了 $u,v$ 之间的边，表示 $u,v$ 被分到了不同集合，付出 $w_i$ 的代价。

由于割容量恰好等于所有被割断边的边权和，而任何一组"选择"都对应一个割，任何割也对应一组合法选择，故最小割就是最小花费。

这个模型在竞赛题中大量出现，例如文末习题中的「Luogu 1361」小 M 的作物（作物种在 A/B 两块田地的收益与共同种植加成）与「SHOI 2007」善意的投票（每个人投票支持/反对，朋友意见相左产生代价）。

五、问题模型 2：最大权值闭合图

5.1 问题描述

给定一张有向图，每个点都有一个权值（可以为正、负或 $0$），需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中（即闭合性：选了点 $u$ 就必须选它的所有出边指向的点）。这样的子图称为闭合图（closure）。

5.2 建图方法

1. 建立超级源点 $s$ 和超级汇点 $t$；
2. 若节点 $u$ 权值为正，则 $s$ 向 $u$ 连一条容量等于该点点权的有向边；
3. 若节点 $u$ 权值为负，则由 $u$ 向 $t$ 连一条容量等于该点点权相反数的有向边；
4. 原图上的所有边容量改为 $\infty$；
5. 跑网络最大流，所有正权值之和减去最大流即为答案，即：

$$ \text{最大闭合子图权值和} = \sum_{w_u>0} w_u - \text{最小割} $$

5.3 正确性证明（四个小结论）

原文档给出了环环相扣的四个结论来证明该建图的正确性：

1. 每一个符合条件的子图都对应流量网络中的一个割。每个割把网络分为两部分，与 $s$ 相连的那部分满足"没有边指向另一部分"（否则那条 $\infty$ 边会造成无限容量），于是满足闭合性要求。该对应是充要的。

2. 最小割所去除的边必须与 $s$ 和 $t$ 其中一者相连。因为原图边的容量为 $\infty$，不可能进入有限的最小割。这保证了割掉的一定是"正权点—$s$"或"$t$—负权点"两类边。

3. 子图权值可写成与割容量的关系式：

$$ \text{子图权值和} = \text{所有正权值之和} - \text{未选择的正权值点的权值之和} + \text{选择的负权值点的权值之和} $$

当我们不选择一个正权值点时，其与 $s$ 的连边会被断开；当我们选择一个负权值点时，其与 $t$ 的连边会被断开。断开的边的边权之和恰好就是割的容量，因此上式化为：

$$ \text{权值和} = \text{所有正权值之和} - \text{割的容量} $$

4. 结论：

$$ \text{最大权值和} = \text{所有正权值之和} - \text{最小割} = \text{所有正权值之和} - \text{最大流} $$

经典应用是「太空飞行计划问题」（见习题）：每个实验有正收益，依赖若干仪器，仪器有购置成本——选择实验必须选择其依赖的仪器，恰好是闭合子图语义；答案为总收益减去最小割。

六、进阶方向与习题练习

6.1 进阶方向

• 平面图最小割与最短路：平面图上的 $s$-$t$ 最小割与其对偶图的最短路存在对应关系，相关讨论见 平面图；
• 全局最小割：无固定源汇的全局最小割不适用本页模型，应使用 Stoer-Wagner 算法；
• 上下界网络流：当边流量存在下界约束时，最小割思路需要推广到上下界网络流模型，见 上下界网络流；
• 最大流算法的更多实现：Edmonds–Karp、ISAP、Push-Relabel/HLPP 等算法的原理与代码均收录于 最大流文档，在卡常或特定数据范围下可作为 Dinic 的替代。

6.2 推荐习题

以下题目覆盖了本页全部技巧（割方案输出、割边数量、二者选其一、最大权值闭合图），来自原文档：

• 「USACO 4.4」Pollutant Control（最小割 + 最少割边数量）
• 「USACO 5.4」Telecowmunication（点割建模，拆点为边）
• 「Luogu 1361」小 M 的作物（二者选其一模型）
• 「SHOI 2007」善意的投票（二者选其一模型）
• 「太空飞行计划问题」（最大权值闭合图 + 方案输出）

建议按"先跑模板题验证最大流最小割定理，再依次尝试两个建图模型"的顺序练习，重点体会"把一个决策问题翻译成割"的建模思维——这比单纯背代码更能应对新题。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki