最小割
概念
割
对于一个网络流图 𝐺 =(𝑉,𝐸)G=(V,E)
，其割的定义为一种 点的划分方式 ：将所有的点划分为 𝑆S 和 𝑇 =𝑉 −𝑆T=V−S 两个集合，其中源点 𝑠 ∈𝑆s∈S，汇点 𝑡 ∈𝑇t∈T．
割的容量
我们的定义割 (𝑆,𝑇)(S,T) 的容量 𝑐(𝑆,𝑇)c(S,T) 表示所有从 𝑆S 到 𝑇T 的边的容量之和，即 𝑐(𝑆,𝑇) =∑𝑢∈𝑆,𝑣∈𝑇𝑐(𝑢,𝑣)c(S,T)=∑u∈S,v∈Tc(u,v)．当然我们也可以用 𝑐(𝑠,𝑡)c(s,t) 表示 𝑐(𝑆,𝑇)c(S,T)．
最小割
最小割就是求得一个割 (𝑆,𝑇)(S,T) 使得割的容量 𝑐(𝑆,𝑇)c(S,T) 最小．
证明
最大流最小割定理
参见 最大流 页面最大流最小割定理一节．
代码
最小割
通过 最大流最小割定理 ，我们可以直接得到如下代码：
参考代码
---|---
### 方案
我们可以通过从源点 𝑠s 开始 DFS，每次走残量大于 00 的边，找到所有 𝑆S 点集内的点．
---|---
割边数量
如果需要在最小割的前提下最小化割边数量，那么先求出最小割，把没有满流的边容量改成 ∞∞，满流的边容量改成 11，重新跑一遍最小割就可求出最小割边数量；如果没有最小割的前提，直接把所有边的容量设成 11，求一遍最小割就好了．
问题模型 1
有 𝑛n 个物品和两个集合 𝐴,𝐵A,B，如果一个物品没有放入 𝐴A 集合会花费 𝑎𝑖ai，没有放入 𝐵B 集合会花费 𝑏𝑖bi；还有若干个形如 𝑢𝑖,𝑣𝑖,𝑤𝑖ui,vi,wi 限制条件，表示如果 𝑢𝑖ui 和 𝑣𝑖vi 同时不在一个集合会花费 𝑤𝑖wi．每个物品必须且只能属于一个集合，求最小的代价．
这是一个经典的 二者选其一 的最小割题目．我们对于每个集合设置源点 𝑠s 和汇点 𝑡t，第 𝑖i 个点由 𝑠s 连一条容量为 𝑎𝑖ai 的边、向 𝑡t 连一条容量为 𝑏𝑖bi 的边．对于限制条件 𝑢,𝑣,𝑤u,v,w，我们在 𝑢,𝑣u,v 之间连容量为 𝑤w 的双向边．
注意到当源点和汇点不相连时，代表这些点都选择了其中一个集合．如果将连向 𝑠s 或 𝑡t 的边割开，表示不放在 𝐴A 或 𝐵B 集合，如果把物品之间的边割开，表示这两个物品不放在同一个集合．
最小割就是最小花费．
问题模型 2
最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 00），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中．
做法：建立超级源点 𝑠s 和超级汇点 𝑡t，若节点 𝑢u 权值为正，则 𝑠s 向 𝑢u 连一条有向边，边权即为该点点权；若节点 𝑢u 权值为负，则由 𝑢u 向 𝑡t 连一条有向边，边权即为该点点权的相反数．原图上所有边权改为 ∞∞．跑网络最大流，将所有正权值之和减去最大流，即为答案．
几个小结论来证明：
- 每一个符合条件的子图都对应流量网络中的一个割．因为每一个割将网络分为两部分，与 𝑠s 相连的那部分满足没有边指向另一部分，于是满足上述条件．这个命题是充要的．
- 最小割所去除的边必须与 𝑠s 和 𝑡t 其中一者相连．因为否则边权是 ∞∞，不可能成为最小割．
- 我们所选择的那部分子图，权值和 == 所有正权值之和 −− 我们未选择的正权值点的权值之和 ++ 我们选择的负权值点的权值之和．当我们不选择一个正权值点时，其与 𝑠s 的连边会被断开；当我们选择一个负权值点时，其与 𝑡t 的连边会被断开．断开的边的边权之和即为割的容量．于是上述式子转化为：权值和 == 所有正权值之和 −− 割的容量．
- 于是得出结论，最大权值和 == 所有正权值之和 −− 最小割 == 所有正权值之和 −− 最大流．
习题
- 「USACO 4.4」Pollutant Control
- 「USACO 5.4」Telecowmunication
- 「Luogu 1361」小 M 的作物
- 「SHOI 2007」善意的投票
- 太空飞行计划问题
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, MegaOwIer, Tiphereth-A, Enter-tainer, Henry-ZHR, ksyx, ouuan, Xeonacid, c-forrest, diauweb, huaruoji, ImpleLee, laocongsc, LuoYisu, Lynricsy, NachtgeistW, Nanarikom, Siyuan 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用