如果说最大流是“如何用最快的速度把水从A送到B”那么最小割就是“如何用最少的代价切断A到B的所有通路”——它用一张网络和一把“剪刀”回答了所有阻断问题的最优解。引言假设你是一名指挥官敌军有一条从后方基地到前线的补给线网络——多条道路交织四通八达。你的任务是炸掉最少的道路或者说花费最小的代价让补给彻底无法送达前线。每条道路的炸毁成本不同你该怎么选这个问题在算法竞赛中有一个标准的数学模型——最小割Minimum Cut。而“最大流等于最小割”这条定理则是解决这类问题的核心武器。你第一天接手三鹿牛奶公司就发生了一件倒霉的事情公司不小心发送了一批有三聚氰胺的牛奶。送货网很大关系复杂坏牛奶已经进入了这个网络。你的任务是在保证坏牛奶不送到零售商节点N的前提下停止某些运输卡车使损失最小——同时在损失最小的前提下还要让停止的卡车数量最少。这就是洛谷 P1344 [USACO4.4] 追查坏牛奶 Pollutant Control要解决的问题。“如果说网络流是图论中的‘水利工程’那么最小割就是它的‘定向爆破’——你不需要关心水怎么流只需要知道在哪里切断最划算。”前置知识在阅读本文之前建议你熟悉以下概念流网络Flow Network一个有向图每条边有容量capacity源点source产生流量汇点sink接收流量。最大流Maximum Flow从源点到汇点能输送的最大流量。增广路Augmenting Path在残留网络中从源点到汇点的一条路径沿它可以增加流量。DFS与BFSDinic算法的基础遍历手段。时间复杂度分析理解算法的渐近复杂度。第一章从“割”说起——最小割是什么1.1 割的定义把图一分为二在一个流网络中一个割Cut就是把所有节点分成两个集合——SS和TT满足源点s∈S汇点t∈T。割的容量Capacity定义为所有从S指向T的边的容量之和。换句话说割的容量就是你为了切断s到t的所有通路需要“剪掉”的那些边的总容量。1.2 最小割最便宜的“断交”方案最小割Minimum Cut就是在所有可能的割中容量最小的那个割。为什么最小割重要因为它回答了一个核心问题切断源点到汇点的所有路径最少需要付出多少代价这正好对应了P1344的第一问——“使坏牛奶无法送达零售商的最小经济损失”。1.3 一个生活中的类比想象一个供水网络自来水厂源点向你家汇点供水中间经过无数管道和水闸。现在政府要检修管道需要关闭一些水闸让你家暂时停水。每个水闸的关闭成本不同——有的闸门锈了很难关成本高有的很好关成本低。最小割就是告诉你关哪些水闸既能让水完全停掉又花最少的钱。这就是最小割的直觉——花最少的代价彻底阻断。第二章最大流最小割定理——解决问题的“核武器”2.1 定理的直观理解最大流最小割定理Max-Flow Min-Cut Theorem是网络流理论中最核心的定理之一在一个流网络中从源点到汇点的最大流量等于最小割的容量。这个定理为什么成立直观上可以这样理解最大流不可能大于最小割因为所有从s到t的流量都必须经过任意一个割而割的容量限制了能通过的总流量。最大流不可能小于最小割如果最大流小于某个割的容量说明网络还没有被充分利用可以继续增广。所以两者必然相等。2.2 定理的证明思路简要严格的证明通常分两步任意流 ≤ 任意割的容量对于任意可行流f和任意割(S,T)流的值等于从S流出的净流量不可能超过割的容量。存在一个流达到最小割的容量当算法如Ford-Fulkerson终止时残留网络中不存在增广路。此时定义S为从源点能到达的所有节点T为其余节点则(S,T)是一个割且其容量恰好等于当前流的值。因此最大流 最小割。2.3 这个定理给我们的“便利”这个定理最大的实用价值在于求最小割等价于求最大流。也就是说我们不需要单独设计一个“求最小割”的算法——只需要跑一遍最大流比如Dinic算法得到的最大流数值就是最小割的容量。在P1344中第一问“最小的经济损失”就是直接跑最大流的结果。第三章P1344的挑战——不仅要最小还要最少3.1 题目的两个要求P1344要求输出两个整数C最小的损失即最小割的容量T在损失最小的前提下最少要停止的卡车数即最小割中包含的边数第一问很简单——直接建图跑最大流。难点在第二问最小割可能有多种方案我们要从中选出边数最少的那一个。也就是说在“最小损失”和“最少停运卡车数”之间前者优先级更高。3.2 朴素思路的问题一个直观的想法是先跑一遍最大流求出最小割的容量然后把所有边的容量改成1再跑一遍最大流得到最少边数。这样做确实可行但要跑两遍网络流代码量大、常数也大。在算法竞赛中我们追求更优雅的一次建图、一次跑流的解法。3.3 核心技巧边权编码既然要同时优化两个目标——主目标损失最小优先级高于辅目标边数最少——我们可以把两个目标“编码”到同一条边的容量中。具体做法是将每条边的容量从 w 改为 w×K1其中 KK 是一个大于总边数 MM 的数。为什么这样做设一个割包含 kk 条边其容量为∑(wi×K1)K×∑wik第一部分 K×∑wi反映的是经济损失主目标第二部分 k 反映的是割边数量辅目标因为 KM≥k所以任何两个割的比较首先看的是 ∑wi 的大小主目标优先只有当 ∑wi 相等时才会比较 k 的大小辅目标。3.4 K 应该取多大题目中 M≤1000所以 K 取1001或更大的数即可。如果 K1001那么任何两个最小割方案只要损失差 ≥1编码后的容量差就至少是 1001远超边数差的最大值 1000主目标一定优先。跑完最大流后ans / K就是最小损失 Cans % K就是最少边数 T。3.5 为什么是 1 而不是 0如果只乘 K 而不加 1那么所有割的编码容量都是 K 的倍数边数信息就丢失了。1的作用就是把边数编码进余数部分——每条被割的边贡献 1总边数就是余数。第四章经典例题精解——洛谷 P1344 追查坏牛奶4.1 题目呈现题目来源洛谷 P1344 [USACO4.4] 追查坏牛奶 Pollutant Control题目描述你第一天接手三鹿牛奶公司就发生了一件倒霉的事情公司不小心发送了一批有三聚氰胺的牛奶。送货网由一些仓库和运输卡车组成每辆卡车都在各自固定的两个仓库之间单向运输牛奶。你的任务是在保证坏牛奶不送到零售商仓库 N的前提下停止某些运输卡车使损失最小。输入格式第一行两个整数 N(2≤N≤32)、M(0≤M≤1000)第 22 到 M1 行每行三个整数 Si,Ei,Ci表示从 Si到 Ei 的一条有向边容量停止损失为 Ci输出格式两个整数 C 和 TC 表示最小的损失T表示在损失最小的前提下最少要停止的卡车数输入样例4 5 1 3 100 3 2 50 2 4 60 1 2 40 2 3 80输出样例60 14.2 建模分析把每个仓库看作节点每辆卡车看作一条有向边边的容量就是停止这辆卡车的经济损失。源点 s1发货工厂汇点 tN零售商目标是让 1 和 N 不连通即找到一个割。最小割的容量就是最小的经济损失。4.3 核心代码C17#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 35; // N 32 const int MAXM 1005; // M 1000 const ll INF 4e18; const ll K 1001; // 大于 M 的大数 struct Edge { int to, rev; ll cap; }; vectorEdge g[MAXN]; int level[MAXN], iter[MAXN]; int n, m; // 添加一条有向边及其反向边 void add_edge(int from, int to, ll cap) { g[from].push_back({to, (int)g[to].size(), cap}); g[to].push_back({from, (int)g[from].size() - 1, 0}); } // BFS 构建层次图 bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int v q.front(); q.pop(); for (auto e : g[v]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[v] 1; q.push(e.to); } } } return level[t] 0; } // DFS 寻找增广路 ll dfs(int v, int t, ll f) { if (v t) return f; for (int i iter[v]; i (int)g[v].size(); i) { Edge e g[v][i]; if (e.cap 0 level[v] level[e.to]) { ll d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; g[e.to][e.rev].cap d; return d; } } } return 0; } // Dinic 最大流 ll max_flow(int s, int t) { ll flow 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); ll f; while ((f dfs(s, t, INF)) 0) { flow f; } } return flow; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 0; i m; i) { int u, v; ll w; cin u v w; // 核心技巧边权编码为 w * K 1 add_edge(u, v, w * K 1); } ll ans max_flow(1, n); cout ans / K ans % K \n; return 0; }4.4 代码详解第34-36行添加边时容量设置为w * K 1。这就是核心的编码技巧。第38-60行标准Dinic算法。bfs构建层次图dfs在层次图上寻找增广路。第67-68行跑完最大流后ans / K得到最小损失主目标ans % K得到最少边数辅目标4.5 样例验证输入样例中M5M5K1001K1001。各边编码后的容量1-3100×100111001013-250×10011500512-460×10011600611-240×10011400412-380×1001180081跑最大流得到 ans60061割掉边2-4容量60边数1。C60061/100160T60061%10011输出60 1与样例一致。4.6 复杂度分析时间复杂度Dinic算法在一般图上的复杂度为 O(V^2E)。本题 V≤32E≤1000完全可行。空间复杂度O(VE)。4.7 另一种思路两遍最大流除了编码技巧也可以分两次建图第一遍按原边权建图跑最大流得到最小损失 C。第二遍将所有边的容量改为1跑最大流得到最少边数 T。这种方法更直观但需要跑两遍代码量略大。编码技巧则一次建图、一次跑流更加简洁高效。总结网络流最小割是算法竞赛中一个极其重要的模型。从“切断补给线”到“追查坏牛奶”它的核心思想始终如一用最小的代价彻底阻断源点到汇点的所有通路。而最大流最小割定理则为我们提供了一个强大的工具——求最小割就是求最大流。P1344这道题的精髓在于多目标优化的处理技巧当我们需要在“主目标最优”的前提下优化“辅目标”时可以通过边权编码的方式把两个目标合并到一条边的容量中一次最大流同时解决两个问题。三个关键点核心定理最大流 最小割求最小割就是求最大流。核心技巧边权编码为 w×K1KM一次最大流同时得到最小割值和最少边数。核心模型凡是“切断所有通路的最小代价”类问题都可以建模为最小割。“最小割教会我们有时候解决问题的最佳方式不是找到最快的路而是找到最便宜的‘断路’——切断有时比连通更需要智慧。”参考文献与延伸阅读《算法导论》Introduction to Algorithms第26章——最大流OI-Wiki网络流 - 最小割洛谷 P1344 [USACO4.4] 追查坏牛奶 Pollutant Control《最小割模型在信息学竞赛中的应用》—— 胡伯涛国家集训队论文HDU 6214 Smallest Minimum Cut—— 同类练习题
