最小割（s–t Min Cut）：在有向/无向带容量图中，给定源 s 与汇 t，求将 s 与 t 分离所需切断的边容量之和的最小值；由最大流最小割定理，最小割值等于最大流值，可在求得最大流后从残量网络中恢复割集。
Description: s–t minimum cut equals maximum flow. After computing a max flow (e.g. Dinic/Edmonds–Karp/Push–Relabel), the source-reachable vertices in the residual graph form the S-side of a minimum cut; edges crossing S→T constitute a min cut. Time: Same as the chosen max-flow algorithm (e.g. Dinic, Edmonds–Karp, Push–Relabel) Status: tested
展开阐述
-
接口/约定（据实现）
- 在执行最大流 calc(s,t) 后：
- 用 BFS/DFS 在残量网络上从 s 出发求可达集 S。
- 割值即为所有 (u∈S, v∉S) 的原始容量之和（考虑有向边）；这些边构成一个最小割。
- 返回：cutValue 与可选的 S（或边列表 cutEdges）。
- 在执行最大流 calc(s,t) 后：
-
核心思路（最大流最小割定理）
- 最大 s–t 流 = 最小 s–t 割。
- 当达到最大流时，残量网络中不存在从 s 到 t 的增广路；此时以 s 为起点的可达集 S 与其补集 T=V\S 构成一个割 (S,T)。
- 所有从 S 指向 T 的边在残量网络中剩余容量为 0（已饱和），其原容量之和即为该最小割值。
-
割集恢复步骤
- 运行最大流（如 057-图论-Dinic最大流 / 060-图论-EdmondsKarp / 076-图论-PushRelabel）。
- 在残量图上从 s 做一次可达性搜索，得到 S。
- 枚举原图边 (u,v)：若 u∈S 且 v∉S，则将其加入 cutEdges，并累加容量得到 cutValue。
-
输出语义
- cutValue：最小割的总容量。
- S/T：一个具体的最小割划分；cutEdges：从 S 到 T 的边集合（可选）。
-
复杂度
- 与最大流相同：如 Dinic 典型 O(E√V)～O(EV^{2/3})（依容量与图类），Edmonds–Karp 为 O(VE^2)，Push–Relabel 近似 O(V^3) 等。
- 额外一次残量图搜索 O(V+E)。
-
使用与注意
- 有向图按有向边判定跨割；无向图通常表示为两条反向有向边。
- 若需求“全局最小割（任意点对）”，参见 064-图论-全局最小割 或 065-图论-GomoryHu树。
- 若考虑费用与流量的权衡，参见 073-图论-最小费用最大流。
- 二分图场景下，最小点覆盖/最大独立集与最小割/最大匹配存在对偶关系（见 075-图论-最小点覆盖、072-图论-最大独立集）。