最大流与最小割面试题

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 最大流题目真正考察的是什么

没有人会被要求凭记忆实现 Dinic 算法。流问题就是建模问题：面试官用平实的语言描述一个情境，整个练习的关键在于你能否意识到它是一个网络，画出正确的网络，并说出能收尾的那个定理。

这就是这类题目被认为不公平的原因。一个背熟了二十道树题的候选人，可能会被“把这五名工程师分配到这五个团队”难倒，因为他从来没能从一个关于人的故事跳到一个带源点和汇点的图。算法是容易的那一半，任何库里都有。

你会遇到的题目，几乎都能归入这四种说法。

下面的所有内容都在这个六节点网络或它的一个小变体上完成，每个数字在印出之前都经过计算，并用第二种方法重新核算过。

2. 模板，以及两个关键方法

把 Dinic 写一遍并保留下来。它大约三十行，速度足以应付面试中的任何题目，而且顺带给出最小割。

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.adj = [], [], [[] for _ in range(n)]

    def add(self, u, v, c):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u] + 1
                    q.append(self.to[e])
        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 = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d
                    self.cap[e ^ 1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

其中有两个细节值得你能解释清楚，因为好的面试官恰恰会追问这些。

第一个是成对存储的边。每条正向边都紧挨着它的反向边存储，所以 e ^ 1 就能在两者之间切换。反向边的初始容量为零，随着推送流量而增长。它存在的意义是让算法能够撤销一个错误的决定：沿反向边送回流量，就抵消了之前正向送出的流量。没有它，贪心选出的第一条路径可能把你困在最优解之下，而这是候选人最常解释不清的一点。

第二个是 self.it，即当前弧优化。一条边在当前阶段被用尽后就再也不会被检查，正是这一点让 Dinic 从二次复杂度降到它所声明的上界。删掉这一行，答案依然正确，但复杂度就被破坏了。

在图中的网络上运行它，答案是 16。在同一网络上运行 Edmonds-Karp 也返回 16，这是最廉价的合理性检查：两个不同的算法，同一个答案。

3. 最大二分图匹配

这是你最可能被问到的题目，通常伪装成排班问题。“五名工程师、五个团队，每名工程师只能去其中一些团队，求最多能安排多少人。”

归约是机械的。加一个源点，向每名工程师连一条容量为 1 的边；加一个汇点，从每个团队连一条容量为 1 的边；再为每一种允许的分配连一条容量为 1 的边。因为容量都是整数，最大流会返回整数解，而值为 k 的整数流恰好就是大小为 k的匹配：源点出发的容量 1 阻止了任何人被使用两次。

def max_matching(left, right, can):
    n = len(left) + len(right) + 2
    s, t = 0, n - 1
    g = Dinic(n)
    for i in range(len(left)):
        g.add(s, 1 + i, 1)
    for j in range(len(right)):
        g.add(1 + len(left) + j, t, 1)
    for i, l in enumerate(left):
        for r in can[l]:
            g.add(1 + i, 1 + len(left) + right.index(r), 1)
    return g.max_flow(s, t)

在图中的实例上，答案是 4，而不是 5。Ada、Ben、Cleo 和 Dan 之间只能到达 backend、data 和 infra，所以三个岗位要容纳四个人，其中一人必然落选。这就是 Hall 条件不成立，能说出它比写出代码更有价值：能让左侧每一个顶点都被匹配的匹配存在，当且仅当左侧的每个子集拥有的邻居数都不少于它的成员数。这里最紧的反例更小：Ada、Cleo 和 Dan 一共只能到达 backend 和 data，三个人争两个岗位。Hall 条件关注的是让一侧饱和，只有两侧大小相同时它才等价于完美匹配，而这里恰好如此。

如果面试官想要的是最快的答案而不是最通用的答案， Hopcroft-Karp 通过同时沿多条最短路径增广，在 O(E√V) 时间内完成。说出它的存在，然后用 Dinic，因为在单位容量图上 Dinic 本来就能达到同样的上界。

4. 藏在匹配中的覆盖

一个很好的追问，也会难倒大多数候选人：“现在告诉我，能触及每一种可能分配的最小人员和团队集合。”

这就是最小顶点覆盖，它在一般图中是 NP 难的。但在二分图中不是， König 定理指出它的大小恰好等于最大匹配。你不需要第二个算法，直接从已有的割中读出覆盖即可。在残量图中从源点做一次搜索，然后取它无法到达的左侧顶点，加上它能够到达的右侧顶点。

在这个实例上得到 Ben、Eve、backend 和 data，共四个顶点，手工检查可以确认九条边都被触及。顶点覆盖的补集是一个独立集，所以最大独立集的大小是 10 − 4 = 6。三个不同的问题，一次最大流调用。

5. 最小割：要的是边，而不只是数值

“最少要切断哪些链路，才能让流量到不了数据中心？”根据定理，这个值就是最大流。但面试官会问是哪些链路，这是另一个更简单的步骤，很多候选人从未学过。

得到最大流之后，从源点出发，沿仍有残量的边做一次搜索。设它到达的集合为 R。最小割就是从 R 指向其补集的所有原始边。

def min_cut(self, s):
    seen = [False] * self.n
    seen[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for e in self.adj[u]:
            if self.cap[e] > 0 and not seen[self.to[e]]:
                seen[self.to[e]] = True
                q.append(self.to[e])
    return [(self.to[e ^ 1], self.to[e])
            for e in range(0, len(self.to), 2)
            if seen[self.to[e ^ 1]] and not seen[self.to[e]]]

在示例网络上，可达集合是 {S, A, B}，割是 A→C （7）加上 B→D （9），总和为 16，正好等于流量值。对全部十六种源点侧子集的暴力枚举确认不存在更便宜的割。

这里有两个陷阱。只统计从可达集合指向不可达集合的边；反向指回的边不在割中。另外，最小割往往不唯一，所以如果被要求给出“那个”割，要说明你返回的是可能的多个割之一，而且它们的值都相同。

6. 不相交路径与 Menger 定理

“从办公室到数据中心有多少条相互独立的路线？”这是一道所有容量都为 1 的流问题。

把每条边的容量设为 1，最大流统计的就是边不相交路径的数量，因为一单位流不能与另一单位流共用一条边。 Menger 定理进一步指出，这个数等于使两个顶点不连通所需删除的最少边数。最大流最小割定理正是这一命题的带权推广。

在单位容量的示例网络上，答案是 2，其中一个最小割是离开源点的两条边，不过有六对不同的边都能做到。与其隐藏，不如指出这一点：在单位容量下，答案往往只是一个度数上界，说出这一点表明你理解这个数字的含义，而不只是会计算它。

如果题目说的是顶点不相交，边上的容量就无法表达它，你需要下面的第一个建模技巧。这里答案同样是 2，而删除 C 和 D 确实会让 T 不可达。有一个前提值得说出来：Menger 定理的顶点形式要求两个端点不相邻，这里满足，因为 S 和 T 之间没有直接相连的边。

7. 把故事变成网络的三个建模技巧

几乎每道流面试题，都是用这些变换之一包装同一个求解器。

顶点有容量。 “这台路由器只能处理 3 个单位。”容量位于边上，所以要拆分顶点：把 v 替换为 v_入 和 v_出，二者之间用一条容量为 3 的边相连；把所有到达 v 的弧改为进入 v_入，把所有离开 v 的弧改为从 v_出出发。把内部容量设为 1，就可以统计顶点不相交路径。

多个源点，多个汇点。 “三个仓库给两家商店供货。”加一个超级源点，向每个真实源点连一条容量无穷大的边，再加一个超级汇点，由每个真实汇点汇入。一次求解器调用就取代了候选人可能开始编写的枚举。

边是无向的。两个方向都以全部容量加入。这看起来像是允许了双倍流量，其实不然，因为残量记账会抵消相反方向上发送的流量。要准备好说出这一点，因为这是个很自然的质疑，而回答很简短。

第四种情况最容易让人栽跟头：下界。“每个司机至少要上两个班”不是容量，标准求解器无法表达它。它需要一个可行循环流的构造，而在面试中有用的做法是把“必须”这个词说出来，而不是把整个构造写成代码。

8. 项目选择，或者说割为什么能选出一个子集

这道题看起来像是动态规划，其实不是，这正是它备受青睐的原因。

“每个项目有已知的收益。每个项目需要某些机器。每台机器有固定成本，并由所有需要它的项目共享。选出收益最高的子集。”

陷阱在于贪心：选取所有收益为正的项目，或者按每台机器的收益排序。两者都不对，因为机器是共享的，一个项目的真实成本取决于你还选了哪些其他项目。

构造很简短。源点到每个项目，容量等于其收益；每台机器到汇点，容量等于其成本；项目到机器，容量为无穷大，使这条边永远不会被割断。于是答案是

最大收益 = (所有收益之和) − (最小割)

，而要选的项目就是位于割的源点一侧的那些。无穷大的边保证了一致性：如果一个项目留在源点一侧，它的机器也必须在那里，否则割就是无穷大。这正是闭合集的定义，而这就是最大闭合子图问题。

在图中的实例上，收益总和为 235，最小割为 195，能达到的最好结果是 40，做法是选 alpha、beta 和 gamma，放弃 delta。Delta 能赚 30，但它是唯一需要 fab 的项目，而 fab 要花 50，所以把它加到另外三个项目中，花的比赚的多 20。对全部十六个子集的暴力枚举结果一致。

9. 棒球淘汰问题

一道经典题，而且不同寻常：朴素的答案不只是慢，而是错的。

给定积分榜和剩余赛程，某支球队还有可能获得第一吗？显而易见的检查是看它可能达到的最好总胜场是否仍超过每个对手当前的总胜场。这能抓住简单情况，却会漏掉有意思的情况，因为对手之间必须相互比赛，而这些比赛总得有人赢。

下面这张表，朴素检查看不出任何问题：

Ducks 最多能达到 79 胜，而目前还没有对手达到 79 胜，所以任何单独比较都无法淘汰他们。但在剩余赛程中，Aces 与 Bolts 还要交手两次，Aces 与 Comets 交手一次，Bolts 与 Comets 交手三次。三个对手之间共有六场比赛，每一场都会让某支球队多一场胜利。

构建一个网络：源点连向每对仍有比赛的球队所对应的节点，容量为它们剩余的比赛场数；每个对局节点以无穷大容量连向它的两支球队；每支球队连向汇点，容量等于它在超过 Ducks 最好情况 79 胜之前还能再赢的场数。只有当六场比赛全都能被吸收，也就是最大流使源点饱和时，Ducks 才能存活。

并不能。流量是 5，而比赛有 6 场，所以有一场比赛无处可去，因此 Ducks 被淘汰了。枚举联赛中所有剩余比赛的全部 2⁹ 种结果可以确认：不存在 Ducks 获得第一的情形，而其余三支球队各自都有这样的情形。

这个缺口还告诉你原因：饱和的球队边指出了那组对手，他们加起来必须赢下的比赛比他们能承受的更多。熟悉这道题的面试官总会要求这个解释。

10. DAG 中的最小路径覆盖

“如果一个工人只能在前后相接的任务之间转移，完成所有这些任务最少需要多少工人？”

这就是最小路径覆盖：覆盖有向无环图中每个顶点所需的最少顶点不相交路径数。它可以用一个值得记住的技巧归约为匹配。把每个顶点拆成左侧的出点副本和右侧的入点副本，为 DAG 的每条边在二分图中加一条边，然后求最大匹配。于是

最小路径覆盖 = 顶点数 − 最大匹配

，因为每条匹配边都连接两个路径片段，从而使路径总数减一。在一个有六个顶点、七条边的 DAG 上，最大匹配是 4，所以最小路径覆盖是 6 − 4 = 2，对所有边子集的穷举搜索结果一致。

有一个限定很重要却常被忽略：这里统计的是顶点不相交的路径。如果路径可以共享顶点，就先求 DAG 的传递闭包，再做同样的归约。

11. 当它是最小费用流而不是最大流时

整个主题中最常见的追问：“现在每种分配都有成本，我要以最便宜的方式安排所有人。”

最大流回答不了这个问题。它最大化的是数量，对两个同样大小的解一视同仁，所以它会毫不犹豫地返回最贵的完美匹配。你需要的是最小费用最大流：在所有取得最大值的流中，找出总费用最小的那个。

对模型的改动很小。每条边除了容量之外再加上单位费用，算法反复沿残量图中最便宜的路径增广，而不是沿最短路径或任意路径。由于残量边带有负费用，普通的 Dijkstra 不能直接使用，所以标准实现要么使用 Bellman-Ford，得到逐次最短路算法，要么维护 Johnson 式的势函数，使 Dijkstra 仍然可用。

关于它，有三点值得能够说出来。

这个特例有专门的名字。一个完全二分图，每种配对都有成本，并要求所有人都被匹配，这就是指派问题，匈牙利算法可以在 O(n³) 时间内解决它。如果面试官的问题恰好是“n 个工人、n 项工作、最小化总成本”，说出匈牙利算法就是期望的答案。

整数性依然成立。在整数容量下，最小费用最大流仍然可以取为整数，这使得加入成本之后，匹配的解释依然有效。

陷阱在于最大化了另一样东西。 “最大化总价值”和“最大化分配数量”不是同一个目标，一个解可能对其中一个最优，而对另一个很差。在动笔之前先问清楚要的是哪一个，因为面试官常常故意含糊其辞，看你是否注意到。

一个值得说出的界限：没有成本，就用最大流；有成本但每一单位都必须流动，就是最小费用流；如果成本在顶点上而不在配对上，你多半又回到了第 8 节的闭合子图问题。

12. 复杂度回答

准备好这些，并准备好说明你实际会用哪一个。

这个警告值得准确地说出来，因为它是常见的追问。 Ford-Fulkerson 是唯一运行时间取决于容量数值而不是图的规模的算法。每条增广路径至少让流量增加 1，所以循环最多执行 maxflow 次；如果容量是十亿，这个上界就是在一个四顶点图上执行十亿次迭代。由于十亿的容量只是十位数字的输入，运行时间相对于输入规模是指数级的。Edmonds-Karp 通过总是选择最短增广路径修正了这一点，完全消除了对容量的依赖。

还有两个事实能加分。整数性：如果每个容量都是整数，就存在一个整数最大流，这正是匹配和不相交路径归约成立的依据。另外，归约的代价：当你从一个故事构建网络时，要按你构建出的网络而不是原始输入来报复杂度。在 n 个人和 m 个岗位上做二分图匹配，会构造出一个有 n + m + 2 个顶点的图，能说出这一点才表明你理解了这个变换。

13. 导致面试失败的错误

忘记反向边。最常见的致命 bug，而且它不会崩溃，只是返回一个过小的数字。如果你解释不了为什么算法需要能够撤销自己之前的决定，你就没有理解这个算法。

重复使用求解器对象。在同一个实例上第二次调用 max_flow 会返回 0，因为残量图已经饱和了。有人计算完流量后想再取一次值来打印，就会以为自己的代码坏了。请新建一个对象，或者缓存结果。

被问集合时却回答数值。 “你会切断哪些链路？”不能用“16”来回答。求出可达集合并列出那些边。

把下界当成容量。 “最多三个班”是容量。“至少两个班”不是，它需要另一种构造。注意“必须”和“至少”这样的词。

把顶点限制建模成边限制。如果约束在机器上而不在链路上，就要拆分顶点。跳过这一步的候选人会得到一个悄悄偏大的答案。

把 Ford-Fulkerson 当作复杂度来报。它是唯一一个在输入规模上可能是指数级的上界。要说出 Dinic 并解释区别。

问题不是流问题时却使用流。最大流不适合求最短路径、生成树，以及任何答案是一条路线而不是一个共享数量的问题。如果没有任何东西被分配或共享，先考虑 BFS、 Dijkstra 或并查集。一个伸手就拿工具箱里最重的锤子的候选人，其实在向面试官透露一些东西。

默不作声地建模。归约就是答案。在白板上画出网络，说出“源点到每名工程师的容量为一，因为没有人能同时做两份工作”，让面试官在你对着错误的模型写出三十行代码之前纠正它。

15. 参考文献

这些题目背后的结果，按时间顺序排列。

1. Menger, K. (1927). “Zur allgemeinen Kurventheorie.” Fundamenta Mathematicae, 10, 96–115.
2. König, D. (1931). “Gráfok és mátrixok.” Matematikai és Fizikai Lapok, 38, 116–119.
3. Hall, P. (1935). “On representatives of subsets.” Journal of the London Mathematical Society, 10(1), 26–30.
4. Ford, L. R. and Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
5. Ford, L. R. and Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
6. Schwartz, B. L. (1966). “Possible winners in partially completed tournaments.” SIAM Review, 8(3), 302–308.
7. Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in networks with power estimation.” Soviet Mathematics Doklady, 11, 1277–1280.
8. Edmonds, J. and Karp, R. M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems.” Journal of the ACM, 19(2), 248–264.
9. Hopcroft, J. E. and Karp, R. M. (1973). “An n^5/2 algorithm for maximum matchings in bipartite graphs.” SIAM Journal on Computing, 2(4), 225–231.
10. Picard, J.-C. (1976). “Maximal closure of a graph and applications to combinatorial problems.” Management Science, 22(11), 1268–1272.
11. Goldberg, A. V. and Tarjan, R. E. (1988). “A new approach to the maximum-flow problem.” Journal of the ACM, 35(4), 921–940.
12. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
13. Wayne, K. D. (2001). “A new property and a faster algorithm for baseball elimination.” SIAM Journal on Discrete Mathematics, 14(2), 223–229.
14. Kleinberg, J. and Tardos, É. (2005). Algorithm Design，第 7 章。Addison-Wesley。
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版，第 26 章。MIT Press。