数据结构与算法 / 系统课时

最小割和最大流怎么对应

最小割和最大流怎么对应

最大流给出“最多能送多少”,最小割解释“为什么再也送不动”。把最大流结束后的残量网络从源点做一次可达性搜索,就能得到一个最小割,并把限制总吞吐量的那组容量边直接找出来。

学习目标

  • 理解割、割容量与任意可行流之间的上界关系。
  • 能从最大流的最终残量网络中恢复一个最小割。
  • 能用割边解释瓶颈,同时避免把单条割边过度解读为唯一根因。

割为什么天然限制最大流

对源点 s 和汇点 t,把全部顶点分成两组:S 包含 s,T 包含 t。所有从 S 指向 T 的原图边构成这个割的正向跨割边,它们的容量总和就是割容量。

任何从 s 送到 t 的流都必须跨过这条边界,所以任意可行流的流量都不会超过任意一个割的容量。换句话说,所有割都在给最大流提供上界,而最小割给出其中最紧的那个上界。

最大流结束后由残量可达性得到最小割

关键点在于:最小割不是靠枚举所有分组找到的。最大流算法结束时,残量网络已经把这个分组“留下来了”。

为什么最终残量图能给出最小割

最大流结束意味着残量网络中不存在从 s 到 t 的路径。此时从 s 出发,只沿剩余容量大于 0 的边搜索,把所有可达点记为 S,不可达点记为 T。

由于 t 不可达,二者确实形成合法的源汇割。更重要的是,任何从 S 指向 T 的原图边都必须已经饱和,否则还有正残量可以跨过去;而任何从 T 指回 S 且承载正向流量的原图边,都会在残量网络产生一条从 S 到 T 的反向残量边,同样与不可达性矛盾。

因此,这个割上的净流量正好等于跨割容量,也等于当前最大流值。于是得到最大流最小割定理:最大流值等于最小割容量。

用程序恢复一个最小割

下面的完整示例先用 Dinic 求最大流,再在最终残量网络里搜索 s 的可达点。为了方便解释结果,同时保留原始边列表,并据此列出从 S 跨到 T 的割边。

python
from collections import deque
from dataclasses import dataclass

@dataclass
class Edge:
    to: int
    rev: int
    cap: int

class Dinic:
    def __init__(self, n: int):
        self.g = [[] for _ in range(n)]
        self.level = [-1] * n
        self.ptr = [0] * n
        self.original_edges = []

    def add_edge(self, u: int, v: int, cap: int) -> None:
        fwd = Edge(v, len(self.g[v]), cap)
        rev = Edge(u, len(self.g[u]), 0)
        self.g[u].append(fwd)
        self.g[v].append(rev)
        self.original_edges.append((u, v, cap))

    def bfs(self, s: int, t: int) -> bool:
        self.level = [-1] * len(self.g)
        self.level[s] = 0
        q = deque([s])

        while q:
            u = q.popleft()
            for e in self.g[u]:
                if e.cap > 0 and self.level[e.to] == -1:
                    self.level[e.to] = self.level[u] + 1
                    q.append(e.to)

        return self.level[t] != -1

    def dfs(self, u: int, t: int, pushed: int) -> int:
        if u == t or pushed == 0:
            return pushed

        while self.ptr[u] < len(self.g[u]):
            e = self.g[u][self.ptr[u]]
            if e.cap > 0 and self.level[e.to] == self.level[u] + 1:
                flow = self.dfs(e.to, t, min(pushed, e.cap))
                if flow > 0:
                    e.cap -= flow
                    self.g[e.to][e.rev].cap += flow
                    return flow
            self.ptr[u] += 1

        return 0

    def max_flow(self, s: int, t: int) -> int:
        # 先求最大流;最终残量网络会被 min_cut 继续使用。
        total = 0
        while self.bfs(s, t):
            self.ptr = [0] * len(self.g)
            while True:
                pushed = self.dfs(s, t, 10**18)
                if pushed == 0:
                    break
                total += pushed
        return total

    def min_cut(self, s: int):
        # 最大流完成后,只沿正残量边找从 s 仍然可达的节点。
        reachable = [False] * len(self.g)
        q = deque([s])
        reachable[s] = True

        while q:
            u = q.popleft()
            for e in self.g[u]:
                if e.cap > 0 and not reachable[e.to]:
                    reachable[e.to] = True
                    q.append(e.to)

        s_side = [v for v, ok in enumerate(reachable) if ok]
        t_side = [v for v, ok in enumerate(reachable) if not ok]
        cut_edges = [
            (u, v, c)
            for u, v, c in self.original_edges
            if reachable[u] and not reachable[v]
        ]
        return s_side, t_side, cut_edges

if __name__ == "__main__":
    dinic = Dinic(4)
    for u, v, c in [
        (0, 1, 4),
        (0, 2, 2),
        (1, 2, 1),
        (1, 3, 2),
        (2, 3, 3),
    ]:
        dinic.add_edge(u, v, c)

    flow = dinic.max_flow(0, 3)
    s_side, t_side, cut_edges = dinic.min_cut(0)

    print("max_flow =", flow)
    print("S_side =", s_side)
    print("T_side =", t_side)
    print("cut_edges =", cut_edges)
    print("cut_capacity =", sum(c for _, _, c in cut_edges))

预期输出

text
max_flow = 5
S_side = [0, 1]
T_side = [2, 3]
cut_edges = [(0, 2, 2), (1, 2, 1), (1, 3, 2)]
cut_capacity = 5

这里的割容量 2 + 1 + 2 = 5,恰好等于最大流值 5。节点 0 和 1 在最终残量网络中仍可从源点到达,但无法再跨过三条已经饱和的割边进入 T 区域。

怎样用最小割解释建模结果

在“容量受限的分配”模型中,最小割给出的不是抽象证明而是瓶颈边界。例如把边理解为机房带宽、仓库出货能力或任务配额,割边集合表示当前所有源汇路径共同绕不过去的容量约束。

但不要把“属于某个最小割”直接理解成“只要扩这一条边,最大流一定增加”。最小割可能不唯一;即使提高一条割边容量,另一组同容量的最小割仍可能继续限制总流量。更可靠的做法是修改容量后重新求最大流和最小割,再观察瓶颈是否迁移。

最容易混淆的两个边界

第一,割容量只统计原图中从 S 指向 T 的边容量,不是把所有跨分区的双向容量都相加。第二,最小割描述的是一组容量约束的整体瓶颈,不等同于单条“最差边”。

当最大流值和最小割容量一致时,你既得到了最优数值,也得到了一个可验证的最优性证据:任何方案都无法超过这个割的容量上界,而当前流已经达到它。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最小割和最大流怎么对应

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通