最小割

What · 是什么

最小割（minimum s-t cut）：把网络点集划分为 S∪T=V、s∈S、t∈T，割容量 c(S,T)=Σ_{u∈S,v∈T} c(u,v)，求最小割容量。最大流最小割定理（Max-flow Min-cut Theorem）指出任意网络的最大流值 = s-t 最小割容量，且最小割的割集可由「残量网络中 s 可达的点集 S」直接读出（S 中所有跨到 T 的边即最小割边）。因此求最小割只需跑一次最大流，再对残量网络从 s DFS/BFS 标记可达点。

Why · 为什么

How · 实现

伪代码

# 1. 建图跑最大流（Dinic）
flow = dinic(s, t)
# 2. 求最小割点集 S*：从 s 在残量网络 DFS 标记可达
vis = [False]*n; vis[s]=True
stack=[s]
while stack:
    u=stack.pop()
    for e in adj[u]:
        if not vis[e.v] and e.cap>0:
            vis[e.v]=True; stack.append(e.v)
# 3. 最小割容量 = flow; 割边 = 所有 (u,v) 满足 vis[u] and not vis[v]

Python 实现

# 最小割 = 最大流 + 残量网络可达性标记。以下依赖 dinic 节点的 Dinic 类。
from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
    def add_edge(self, u, v, cap):
        self.adj[u].append([v, cap, len(self.adj[v])])
        self.adj[v].append([u, 0, len(self.adj[u]) - 1])
    def _bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, rev in self.adj[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0
    def _dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.adj[u]):
            e = self.adj[u][self.it[u]]
            v, cap, rev = e
            if cap > 0 and self.level[v] == self.level[u] + 1:
                pushed = self._dfs(v, t, min(f, cap))
                if pushed:
                    e[1] -= pushed
                    self.adj[v][rev][1] += pushed
                    return pushed
            self.it[u] += 1
        return 0
    def max_flow(self, s, t):
        flow = 0
        INF = 10 ** 18
        while self._bfs(s, t):
            self.it = [0] * self.n
            while True:
                pushed = self._dfs(s, t, INF)
                if not pushed:
                    break
                flow += pushed
        return flow
    def min_cut_set(self, s):
        """返回残量网络中 s 可达的点集（最小割 S* 侧）."""
        vis = [False] * self.n
        vis[s] = True
        stack = [s]
        while stack:
            u = stack.pop()
            for v, cap, rev in self.adj[u]:
                if cap > 0 and not vis[v]:
                    vis[v] = True
                    stack.append(v)
        return vis


if __name__ == "__main__":
    # 图: s=0,t=3; 0->1(3) 0->2(3) 1->2(2) 1->3(3) 2->3(3); 最大流=最小割=6
    g = Dinic(4)
    g.add_edge(0, 1, 3); g.add_edge(0, 2, 3)
    g.add_edge(1, 2, 2); g.add_edge(1, 3, 3); g.add_edge(2, 3, 3)
    flow = g.max_flow(0, 3)
    S = g.min_cut_set(0)
    # 割边 = u in S, v not in S
    cut_edges = []
    for u in range(4):
        for v, cap, rev in g.adj[u]:
            if S[u] and not S[v]:
                cut_edges.append((u, v))
    print("maxflow =", flow)
    print("S =", [i for i in range(4) if S[i]])
    print("cut_edges =", cut_edges)
    assert flow == 6

易错点

• 最大流跑完后直接读 flow 作为最小割容量即可，但求割边集必须用残量网络可达性，不能想当然
• 「最小割前提下割边最少」需二次建图重跑，不要直接数满流边
• 二者选其一建模：连 s 边权 a_i、t 边权 b_i、u-v 双向 w，注意方向与割语义
• 最大权闭合图：正权连 s、负权连 t、原图边权 INF，答案是正权和-最小割
• 拆点（点割）时：每个点拆成入点→出点容量 1，原边容量 INF

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/flow/min-cut.md
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/flow/max-flow.md
• 书籍✓ CPH ch20 pp191-204