分类
Level9

最小割

一、最小割的核心概念

最小割（Minimum Cut）是网络流理论中的关键概念，用于描述将图的顶点划分为两个互不相交的集合（含源点s的集合S和含汇点t的集合T），使得从S到T的边权之和最小的割集。简单来说，最小割是“断开源汇连通性的最小代价”。

1. 形式化定义

对于带权有向图G=(V,E,c)（c(u,v)为边(u,v)的容量），割是指将顶点集V划分为S和T=V∖S（s∈S, t∈T），记割集为cut(S,T)。割的容量为：

∣c(S,T)∣=u∈S,v∈T∑​c(u,v)

即所有从S指向T的边的容量之和（反向边不计入）。最小割是所有可能割集中容量最小的那个，记为mincut(s,t)。

2. 与最大流的关系：最大流最小割定理

最小割的核心性质是与最大流等价，即：

最大流(s,t)=最小割(s,t)

该定理是网络流理论的基石，它将“求最大流”与“求最小割”两个问题统一起来——通过求解最大流，可直接得到最小割的容量；反之，最小割的容量也是最大流的上限（任何流都无法超过最小割的容量）。

二、最小割的重点知识

1. 割的分类与性质

  • 有向图 vs 无向图：有向图的割仅计算从S到T的边；无向图的割需计算所有跨集合的边（无论方向），容量为边权之和。
  • 割的唯一性：最小割可能不唯一（如存在多条边容量相同且均为最小割的一部分），但容量唯一。
  • 割边性质：最大流后，割边必满流（即流量等于容量）；非割边的流量小于容量。

2. 最小割的求解算法

  • 基于最大流算法： 最常用的方法是先求最大流，再从残量网络中找割。具体来说：
    1. 用Dinic、Edmonds-Karp等算法求出从s到t的最大流；
    2. 在残量网络中，从s出发进行DFS/BFS，标记所有可达节点（属于集合S）；
    3. 未被标记的节点属于集合T，所有从S到T的边构成最小割。 这种方法的正确性由最大流最小割定理保证，且能直接得到最小割的具体边集。
  • 全局最小割算法： 若需找整个图的全局最小割（不固定源汇点），需用专门算法，如：
    • Stoer-Wagner算法：通过迭代合并顶点，每次求当前图的“最小割”，最终得到全局最小割，时间复杂度为O(n3)（n为顶点数）；
    • Karger算法：随机收缩边，通过概率方法求最小割，适用于大规模图（平均时间复杂度为O(n2logn)）。

3. 最小割的常见模型

  • 最大权闭合图： 闭合图是指“若选顶点u，则必须选其所有后继顶点”的子图。最大权闭合图是权值和最大的闭合图，可通过最小割求解：
    1. 构建网络：添加源点s（连接所有正权点，容量为权值）、汇点t（所有负权点连接t，容量为权值绝对值）、原图中的边（容量无穷大）；
    2. 求最小割：用最大流算法求出最小割，所有正权之和减去最小割即为最大权闭合图的权值和。
  • 二分图的最小点权覆盖集： 点覆盖集是指“覆盖所有边的点集”，最小点权覆盖集是权值和最小的点覆盖集。对于二分图，可通过最小割转化为：
    1. 将二分图左部点连接源点（容量为点权），右部点连接汇点（容量为点权）；
    2. 原图中的边（左部到右部）容量设为无穷大；
    3. 最小割的容量即为最小点权覆盖集的权值和。
  • 无向图点连通度： 点连通度是指“使图不连通所需移除的最少点数”。对于无向图，可通过最小割转化为网络流问题：
    1. 将每个顶点拆分为入点u和出点u′，连接u到u′（容量1）；
    2. 原图中的边(u,v)转化为u′→v和v′→u（容量无穷大）；
    3. 固定源点s，枚举汇点t（与s不相邻），求最大流，最小的最大流即为点连通度。

三、最小割的学习方法

1. 基础铺垫：掌握最大流算法

最小割的学习依赖最大流的基础，需先掌握：

  • 最大流算法：如Dinic（分层图+阻塞流）、Edmonds-Karp（BFS增广），重点理解残量网络、增广路径等概念；
  • 最大流最小割定理：深刻理解“最大流等于最小割”的本质（割是流的瓶颈）。

2. 核心技能：求解最小割的步骤

  • 步骤1：针对具体问题，构建网络流模型（如添加源汇点、处理点权/边权）；
  • 步骤2：用最大流算法（如Dinic）求出最大流；
  • 步骤3：在残量网络中标记源点可达节点（S集合），未被标记的节点为T集合；
  • 步骤4：提取所有从S到T的边，即为最小割。

3. 专项练习：从经典题到变形题

  • 入门题：
    • 洛谷P3376（网络最大流模板）：通过求最大流，理解最小割与最大流的关系；
    • POJ 2914（全局最小割）：用Stoer-Wagner算法练习全局最小割的求解。
  • 进阶题：
    • 洛谷P2762（太空飞行计划问题）：最大权闭合图的经典题，通过最小割求解；
    • 洛谷P2774（方格取数问题）：二分图最小割模型，练习点覆盖集的应用。
  • 难题：
    • HDU 6598（Harmonious Army）：混合图的最小割问题，需处理有向边和无向边的转化；
    • CF103E（Buying Sets）：集合选择的最小割模型，练习复杂网络流的构建。

4. 参考资料与工具

  • 书籍与博客：《图论导引》（网络流章节）、Amber论文《最小割模型在信息学竞赛中的应用》、OI-wiki“最小割”专题；
  • 在线平台：LeetCode（网络流标签）、洛谷（最小割专题）、Codeforces（Div.1+ 最小割题）；
  • 工具：NetworkX（Python图论库，支持最大流/最小割计算）、Dinic模板（竞赛常用）。

四、总结

最小割的核心是“断开源汇的最小代价”，其与最大流的等价性是解决问题的关键。学习时需从基础的最大流算法入手，掌握最小割的求解步骤（最大流→残量网络→标记集合→提取割边），并通过专项练习（如最大权闭合图、二分图点覆盖）提升建模能力。推荐的练习顺序是：模板题→经典模型题→复杂变形题，最终实现“看到问题就能想到用最小割建模”的目标。