最小割问题完全指南最大流最小割定理、建图模型与 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$ 和 $TV-S$ 两个集合其中源点 $s\in S$汇点 $t\in T$。在 网络流简介 中这一概念以更形式化的方式给出若 ${S,T}$ 是 $V$ 的划分即 $S\cup TV$ 且 $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$ 上可达的点集$TV\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::queueint 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$ 层流向第 $d1$ 层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 附加技巧最小化割边数量原文档还给出一个高频技巧——在最小割前提下最小化割边数量先求出原图的最小割跑一遍最大流把没有满流的边容量改成 $\infty$把满流的边容量改成 $1$重新跑一遍最小割得到的数值即为最小割边数量。原理是第一遍求解后满流的边才是候选割边第二遍建图让每条候选割边代价为 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 建图方法这是经典的二者选其一最小割模型对每个集合建立超级源点 $s$ 和超级汇点 $t$第 $i$ 个点由 $s$ 连一条容量为 $a_i$ 的边向 $t$ 连一条容量为 $b_i$ 的边对每个限制条件 $(u,v,w)$在 $u,v$ 之间连容量为 $w$ 的双向边答案 最大流 最小割容量。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 建图方法建立超级源点 $s$ 和超级汇点 $t$若节点 $u$ 权值为正则 $s$ 向 $u$ 连一条容量等于该点点权的有向边若节点 $u$ 权值为负则由 $u$ 向 $t$ 连一条容量等于该点点权相反数的有向边原图上的所有边容量改为 $\infty$跑网络最大流所有正权值之和减去最大流即为答案即$$ \text{最大闭合子图权值和} \sum_{w_u0} w_u - \text{最小割} $$5.3 正确性证明四个小结论原文档给出了环环相扣的四个结论来证明该建图的正确性每一个符合条件的子图都对应流量网络中的一个割。每个割把网络分为两部分与 $s$ 相连的那部分满足没有边指向另一部分否则那条 $\infty$ 边会造成无限容量于是满足闭合性要求。该对应是充要的。最小割所去除的边必须与 $s$ 和 $t$ 其中一者相连。因为原图边的容量为 $\infty$不可能进入有限的最小割。这保证了割掉的一定是正权点—$s$或$t$—负权点两类边。子图权值可写成与割容量的关系式$$ \text{子图权值和} \text{所有正权值之和} - \text{未选择的正权值点的权值之和} \text{选择的负权值点的权值之和} $$当我们不选择一个正权值点时其与 $s$ 的连边会被断开当我们选择一个负权值点时其与 $t$ 的连边会被断开。断开的边的边权之和恰好就是割的容量因此上式化为$$ \text{权值和} \text{所有正权值之和} - \text{割的容量} $$结论$$ \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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
最小割问题完全指南：最大流最小割定理、建图模型与 OI 实战（OI-wiki）
最小割问题完全指南最大流最小割定理、建图模型与 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$ 和 $TV-S$ 两个集合其中源点 $s\in S$汇点 $t\in T$。在 网络流简介 中这一概念以更形式化的方式给出若 ${S,T}$ 是 $V$ 的划分即 $S\cup TV$ 且 $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$ 上可达的点集$TV\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::queueint 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$ 层流向第 $d1$ 层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 附加技巧最小化割边数量原文档还给出一个高频技巧——在最小割前提下最小化割边数量先求出原图的最小割跑一遍最大流把没有满流的边容量改成 $\infty$把满流的边容量改成 $1$重新跑一遍最小割得到的数值即为最小割边数量。原理是第一遍求解后满流的边才是候选割边第二遍建图让每条候选割边代价为 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 建图方法这是经典的二者选其一最小割模型对每个集合建立超级源点 $s$ 和超级汇点 $t$第 $i$ 个点由 $s$ 连一条容量为 $a_i$ 的边向 $t$ 连一条容量为 $b_i$ 的边对每个限制条件 $(u,v,w)$在 $u,v$ 之间连容量为 $w$ 的双向边答案 最大流 最小割容量。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 建图方法建立超级源点 $s$ 和超级汇点 $t$若节点 $u$ 权值为正则 $s$ 向 $u$ 连一条容量等于该点点权的有向边若节点 $u$ 权值为负则由 $u$ 向 $t$ 连一条容量等于该点点权相反数的有向边原图上的所有边容量改为 $\infty$跑网络最大流所有正权值之和减去最大流即为答案即$$ \text{最大闭合子图权值和} \sum_{w_u0} w_u - \text{最小割} $$5.3 正确性证明四个小结论原文档给出了环环相扣的四个结论来证明该建图的正确性每一个符合条件的子图都对应流量网络中的一个割。每个割把网络分为两部分与 $s$ 相连的那部分满足没有边指向另一部分否则那条 $\infty$ 边会造成无限容量于是满足闭合性要求。该对应是充要的。最小割所去除的边必须与 $s$ 和 $t$ 其中一者相连。因为原图边的容量为 $\infty$不可能进入有限的最小割。这保证了割掉的一定是正权点—$s$或$t$—负权点两类边。子图权值可写成与割容量的关系式$$ \text{子图权值和} \text{所有正权值之和} - \text{未选择的正权值点的权值之和} \text{选择的负权值点的权值之和} $$当我们不选择一个正权值点时其与 $s$ 的连边会被断开当我们选择一个负权值点时其与 $t$ 的连边会被断开。断开的边的边权之和恰好就是割的容量因此上式化为$$ \text{权值和} \text{所有正权值之和} - \text{割的容量} $$结论$$ \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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
