1. 从水管网络到最大流一个接地气的开场干了这么多年算法和优化相关的工作我发现一个挺有意思的现象很多听起来高大上的概念比如“最大流”和“最小割”其实就藏在我们每天都能见到的生活场景里。想象一下你们小区的自来水供水系统或者更简单点你家里连接着花洒的那段水管网络。水源比如水塔或水泵就是起点你家花洒的出水口就是终点中间那些粗细不一、可能还有阀门控制的水管以及它们之间的连接点就构成了一张“网络图”。现在我问你在现有管道不爆管、阀门全开的情况下从水源到你家花洒单位时间内最多能流过来多少水这个“最大水流量”就是“最大流”问题最朴素的描述。那“最小割”又是什么咱们继续这个水管例子。假如有个调皮孩子想搞个恶作剧让你家停水但他力气有限每次只能切断几根水管。他的目标是让你家彻底没水同时希望自己切断的水管“总代价”最小——比如切断粗水管很费劲代价大切断细水管轻松些代价小。那么他应该切断哪几根水管才能用最小的“力气”达成停水的目的这个“需要切断的、代价最小的水管集合”就是“最小割”。最神奇的是在任何网络中最大流的值永远等于最小割的容量。这个听起来有点反直觉的结论就是著名的“最大流最小割定理”它是整个网络流理论的基石。这篇文章我就想用这种“说人话”的方式带你彻底搞懂这两个核心概念。无论你是正在啃《算法导论》的学生还是工作中偶尔需要处理资源调度、路径规划的工程师理解了这个框架很多问题都会豁然开朗。咱们不堆公式就用生活化的类比和一步步的推演把原理、算法和实际怎么用掰开揉碎了讲清楚。最后还会聊聊它的一个高级变种——“最小费用最大流”看看当流量“打车”要付“路费”时我们该如何精打细算。2. 核心概念拆解图、流与割在进入算法之前我们必须把几个最基础的定义像搭积木一样摆清楚。这些定义是后面所有推理和操作的“普通话”版本理解了它们你就读懂了网络流这门语言的字母表。2.1 网络图水管系统的地图首先我们得有一张“地图”。在网络流问题中这张地图叫做流网络本质上就是一个有向图。它包含以下几个要素节点就是地图上的点代表交叉路口、中转站。在我们水管模型里它就是水管之间的连接处、水泵、水塔、你家水表的位置。特别地我们规定其中一个是源点用s表示就是水源另一个是汇点用t表示就是最终的目的地比如你家花洒。有向边就是连接两个节点的、有方向的管道。从节点u指向节点v的边表示物质水、车、数据包可以从u流向v。边是单向的这很符合现实——水不能自己从低处往高处倒流除非有水泵但那可以建模为另一个节点和边。容量这是贴在每条边上的“标签”表示这条管道在单位时间内最多能允许通过多少“东西”。记作c(u, v)必须是非负实数。它就像水管的粗细或者公路的车道数。容量是边的固有属性是理论上的上限。这里有个关键点在基本的最大流问题中我们通常不允许有反向的边即如果存在(u, v)就不会有(v, u)或者即使有也视为两条独立的边。这是为了简化初始模型。后面我们会看到算法如何巧妙地“模拟”出反向流动。注意很多初学者会混淆“实际流量”和“容量”。容量是固定的、理论上的最大值就像水管的最大直径。而实际流量是我们需要计算和分配的、在容量限制下的一个动态值。2.2 什么是“流”规则比想象中严格现在我们要往这个水管网络里“注水”了。所谓的一个可行流就是给每条边分配一个流量值f(u, v)它必须满足三条非常合理且严格的“交通规则”容量限制对任意边(u, v)0 ≤ f(u, v) ≤ c(u, v)。这太好理解了流过一条边的流量不能超过它的容量也不能是负数基本模型中我们不允许倒流。流量守恒对于除了源点s和汇点t之外的任何一个中间节点流入这个节点的总流量必须等于流出这个节点的总流量。用公式表达就是∑f(u, i) ∑f(i, v)。这意味着水流在中间节点既不能无故产生也不能无故消失。所有从源点泵出的水最终都必须一滴不差地流到汇点中途没有损耗和囤积。这个规则是网络流合理性的核心保障。斜对称性这个规则在基础定义里有点“形式化”但它为后续算法提供了巨大便利。它规定f(u, v) -f(v, u)。意思是如果你认为从u到v流了 5 个单位那么从v到u的流量就记为 -5。在初始没有反向边的情况下f(v, u)通常就是 0。这个定义主要是为了数学上的统一在算法实现中它允许我们用“残量网络”中的反向边来记录“可以退回的流量”非常巧妙。一个可行流的总流量值|f|定义为从源点s净流出的流量也等于流入汇点t的净流量。最大流问题就是在所有可行流中找到那个总流量|f|最大的流。2.3 什么是“割”一把精准的手术刀“割”的概念比“流”要抽象一点但用“切断”来想就直观了。一个s-t割把整个网络图的节点分成两个不相交的集合S和T其中源点s在S里汇点t在T里。你可以想象用一把刀沿着节点之间的“缝隙”切下去把图切成左右两半s在左边 (S)t在右边 (T)。那么所有从左边S指向右边T的边就被这把刀“切断”了。这些被切断的边构成了这个割的割边集。这个割的容量定义为所有从S指向T的边的容量之和记作c(S, T) ∑ c(u, v)其中u∈S, v∈T。注意容量只关心从S到T的边不关心反方向的边从T到S。割的容量可以理解为“为了彻底断绝s和t之间的联系所需要切断的边的总理论最大通行能力”。那么最小割问题就是在所有可能的s-t割中找到那个容量c(S, T)最小的割。回到恶作剧孩子的例子最小割就是他切断水管“总粗细”总容量最小的那个方案。2.4 最大流最小割定理一个震撼的等式这是网络流理论中最优美、最重要的结论在任何流网络中从 s 到 t 的最大流值等于分隔 s 和 t 的所有割的最小容量。即max |f| min c(S, T)这个定理为什么重要它建立了“全局优化问题”最大流和“组合结构问题”最小割之间的等价桥梁。它告诉我们上界性任何流的流量都不可能超过任何一个割的容量。因为所有从s到t的流量必须穿过割边集而割边集的总容量是有限的。所以最大流 ≤ 最小割。可达性算法可以找到一个流和一个割使得流的流量等于割的容量。这就证明了等号可以成立因此最大流 最小割。在算法层面这意味着当我们用某种方法比如接下来要讲的Ford-Fulkerson方法求出了最大流的同时我们几乎可以“免费”地得到一个最小割。这个最小割就是算法结束后在“残量网络”中从源点s还能到达的节点集合S以及剩下的节点集合T。所有从S指向T的、且在原网络中容量已满即残量网络中对应边容量为0的边就构成了一个最小割集。这个特性在图像分割、网络可靠性分析等领域有直接应用。3. 核心算法解析Ford-Fulkerson 方法与 Edmonds-Karp 实现理解了概念我们来看怎么算。最经典、最直观的算法框架是Ford-Fulkerson 方法。它不是某一个具体算法而是一个思想框架“只要存在一条从源点到汇点的、每条边上都有剩余容量的路径称为增广路径我们就沿着这条路尽可能多地增加流量。”3.1 残量网络算法的舞台这是理解所有增广路算法的关键。对于当前的一个可行流f我们构造一个残量网络G_f。这个网络和原图有相同的节点但边和容量定义不同对于原图中的每条边(u, v)如果当前流量f(u, v) c(u, v)那么在残量网络中我们创建一条从u到v的正向边其剩余容量为c_f(u, v) c(u, v) - f(u, v)。这表示这条边还能再通过多少流量。同时我们创建一条从v到u的反向边其剩余容量为c_f(v, u) f(u, v)。这表示我们可以“退回”多少已分配的流量。反向边是算法能“反悔”、找到全局最优解的核心机制。一个生活化比喻把网络想象成一个单行道系统正向边但每开通一条单行道我们就同步修建一条平行的、仅供“掉头车”使用的应急车道反向边。应急车道的宽度等于当前单行道上的车流量。当我们发现另一条路更优时就可以让一部分车从应急车道掉头腾出空间给新的车流。反向边记录的正是这种“可退让”的潜力。3.2 增广路径与算法步骤在残量网络G_f中任何一条从s到t的、每条边剩余容量都大于0的路径就是一条增广路径。这条路径的“瓶颈”是路径上所有边剩余容量的最小值记作bottleneck。Ford-Fulkerson 方法的步骤可以概括为初始化所有边流量为0。在残量网络G_f中寻找一条从s到t的增广路径p。如果找不到算法结束当前流就是最大流。找到路径p的瓶颈容量bottleneck。对于路径p上的每一条边(u, v)如果它是正向边在原图中存在则增加其流量f(u, v) bottleneck。如果它是反向边对应原图中(v, u)的退回则减少原边的流量f(v, u) - bottleneck。这等价于在残量网络中正向边容量减少反向边容量增加。更新残量网络G_f返回步骤2。为什么反向边是灵魂看一个经典例子一个“X”形网络s连接A和BA和B都连接t同时s也直接连接t。如果不用反向边我们可能先找到路径 s-A-t把流量占满导致更优的全局方案 s-B-t 和 s-A-B-t 无法实现。有了反向边当我们后来找到路径 s-B-A-t 时可以通过A-t的反向边对应原图A-t的流量退回一部分流量转而从A流向B再流向t从而腾出s-A的容量给新的流量实现全局流量最大化。反向边提供了“重新路由”的可能性。3.3 Edmonds-Karp 算法用BFS保证效率基础的Ford-Fulkerson方法没有规定如何“寻找增广路径”。如果使用DFS随意寻找在最坏情况下比如容量是无理数算法可能永远不会终止或者效率极低复杂度与流量值有关不是多项式时间。Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个具体、高效的实现。它规定每次使用广度优先搜索在残量网络中寻找最短的增广路径即边数最少的路径。这一简单的策略带来了质的飞跃时间复杂度被证明为O(V * E^2)其中V是节点数E是边数。这是一个严格的多项式时间算法与边的容量大小无关。工作原理BFS 每次都找到边数最少的路径进行增广。这避免了 DFS 可能陷入的“长路径漩涡”能更快地扩大流量并且保证了算法在有限步内结束。实操心得在99%的编程竞赛和日常工程问题中当你需要实现最大流时Edmonds-KarpEK算法是首选的起点。它实现简单只需要BFS易于调试对于节点和边数在几百到几千规模的问题通常足够快。下面是一个高度简化的 EK 算法核心流程的伪代码描述帮助你理解其结构# 假设使用邻接表存储图每条边记录 (to, capacity, reverse_edge_index) def edmonds_karp(s, t): max_flow 0 while True: # 使用BFS寻找最短增广路径并记录路径上前驱节点和瓶颈值 queue [s] prev_node [-1] * N # 记录路径上前一个节点 prev_edge [-1] * N # 记录到达当前节点的边的索引 flow_to [0] * N # 记录到当前节点的路径上的最小剩余容量 flow_to[s] INF found False while queue and not found: u queue.pop(0) for i, (v, cap, rev) in enumerate(graph[u]): if cap 0 and prev_node[v] -1 and v ! s: # 有剩余容量且未访问 prev_node[v] u prev_edge[v] i flow_to[v] min(flow_to[u], cap) if v t: found True break queue.append(v) if not found: # 没有增广路了 break # 找到了增广路瓶颈值为 flow_to[t] bottleneck flow_to[t] max_flow bottleneck # 沿着路径更新残量网络 v t while v ! s: u prev_node[v] edge_idx prev_edge[v] # 减少正向边容量 graph[u][edge_idx].capacity - bottleneck # 增加反向边容量 (通过反向边索引找到) rev_edge_idx graph[u][edge_idx].rev graph[graph[u][edge_idx].to][rev_edge_idx].capacity bottleneck v u return max_flow注意事项在实现时存储反向边的技巧至关重要。通常我们在加边时同时加入正向边和反向边并互相记录对方的索引。这样在更新流量时可以O(1)地找到对应的反向边进行操作。这是实现中的关键细节容易出错。4. 算法实现细节与优化策略理解了 EK 算法的骨架我们深入到实现层面看看有哪些坑要避开以及如何让它跑得更快。4.1 数据结构的选择与边的存储网络流算法的性能与图的数据结构紧密相关。邻接矩阵在边非常稠密时可能简单但对于稀疏图大多数实际情况会浪费大量空间且寻找邻接边效率低。邻接表是绝对的主流选择。更具体地说我们通常使用“链式前向星”或“动态数组邻接表”来存储。每条边需要存储以下信息to: 边的终点。cap: 边的当前剩余容量注意是残量网络中的容量。flow: 当前流量有时可以不显式存储通过初始容量和当前容量推算。rev: 反向边在邻接表中的索引。这是实现的关键。加边的操作需要成对进行def add_edge(u, v, capacity): graph[u].append(Edge(tov, capcapacity, revlen(graph[v]))) graph[v].append(Edge(tou, cap0, revlen(graph[u])-1)) # 反向边初始容量为0初始化反向边容量为0符合初始流量为0的设定。当沿着正向边推送流量时减少其cap并增加对应反向边的cap这个反向边的cap就代表了可以退回的流量。4.2 寻找增广路径的BFS实现要点在 EK 算法中BFS 不仅要判断能否到达汇点t还必须记录路径以便回溯更新。通常我们用两个数组pre和pre_edge来实现pre[v]记录在 BFS 树中节点v是从哪个节点u访问过来的。pre_edge[v]记录是通过节点u的邻接表中的第几条边访问到v的。这样当 BFS 到达t后我们可以从t开始利用pre数组回溯到s同时用pre_edge找到具体是哪条边从而确定整条增广路径和瓶颈容量。一个常见的坑在 BFS 中判断条件必须是“边的剩余容量cap 0”才将其加入队列。这意味着我们只走还有“空间”的边。同时需要标记已访问节点防止走回头路和形成环路。4.3 Dinic 算法更强大的优化当图的规模更大节点/边数上万时EK 算法的O(V*E^2)复杂度可能显得吃力。Dinic 算法是更高效的选择平均表现和理论上限都更好时间复杂度为O(V^2 * E)对于单位容量图甚至能达到O(min(V^(2/3), E^(1/2)) * E)。Dinic 算法的核心思想是“分层图”“多路增广”BFS 构建分层图从源点s出发进行 BFS记录每个节点到s的最短距离层数。在残量网络中只保留从第i层指向第i1层的边。这保证了我们找到的路径都是最短的并且为后续 DFS 提供了清晰的指引。DFS 进行多路增广在分层图上进行 DFS寻找从s到t的路径。Dinic 的 DFS 是“阻塞流”式的它会尝试一次性找到多条增广路径并尽可能压榨每条路径的流量。DFS 过程中如果一个节点的出边已经无法推送更多流量就将其从当前分层图中临时移除称为“当前弧优化”避免后续 DFS 重复访问无效边。当前弧优化是 Dinic 算法的关键优化。在每次 DFS 中对每个节点维护一个指针指向下一条待尝试的边。当一条边被榨干剩余容量为0后指针就移动到下一条边。这样在整个算法过程中每条边最多被访问一次在构建阻塞流的那一轮 BFS-DFS 周期内极大地提高了效率。实操心得对于算法竞赛或高性能场景Dinic 是标配。它的实现比 EK 稍复杂但模板化程度很高。一旦掌握大部分网络流题目都能解决。它的性能优势在稀疏图、尤其是带有某种特征如二分图匹配转化来的流网络的图上非常明显。如果你发现 EK 算法超时升级到 Dinic 通常是第一选择。4.4 最小割的求解如前所述当最大流算法运行结束后在最终的残量网络G_f中从源点s出发只经过剩余容量cap 0的边所能到达的所有节点构成集合S。剩下的节点构成集合T。那么所有起点在S、终点在T、且在原网络中容量不为0的边就组成了一个最小割集。为什么这就是最小割因为算法结束后S和T之间所有边的剩余容量都为0这意味着这些边在原网络中的流量已经达到了满容量。根据最大流最小割定理这个割的容量正好等于最大流的值因此它必然是一个最小割。在代码实现上只需要在得到最大流后从s开始做一次 BFS 或 DFS只遍历cap 0的边就能标记出集合S。然后遍历原图的所有边如果一条边的起点在S终点不在S且原容量大于0那么这条边就在最小割集中。5. 从理论到应用经典问题建模实战最大流最小割不是空中楼阁它是一把强大的瑞士军刀可以巧妙解决许多看似不相关的组合优化问题。关键在于如何将实际问题“建模”成一个流网络。5.1 二分图最大匹配问题这是最经典的应用之一。问题描述有两组节点左集L和右集R中间有一些边连接左右节点。求一个最大的边集使得这个边集中的任意两条边都没有公共端点即每个节点最多被匹配一次。建模方法创建超级源点s用容量为1的边连接到左集L的每一个节点。创建超级汇点t用容量为1的边从右集R的每一个节点连接到t。将原有的左集到右集的边全部设置为容量为1的边。在这个新网络上跑最大流得到的最大流值就是最大匹配数。流量为1的边从L到R的边就对应了一组匹配。为什么有效容量为1的边保证了每个左节点最多流出一个单位流量匹配一条边每个右节点最多流入一个单位流量被匹配一次。从s到t的流自然就对应了一个合法的匹配方案。最大流即最大匹配。5.2 多源点多汇点问题有时不止一个起点或终点。例如一个城市有多个水库源点和多个居民区汇点问整个系统最大的供水总量。建模方法创建一个虚拟的超级源点S用容量为无穷大或该水源的实际最大供应量的边连接到所有真实源点。同样创建一个虚拟的超级汇点T用容量为无穷大或该居民区的最大需求的边从所有真实汇点连接到T。然后在新图上求从S到T的最大流即可。5.3 点容量问题在基本模型中容量限制在边上。但有时节点也有容量限制比如一个中转站每小时只能处理一定数量的货物。建模方法使用“拆点”技巧。将原节点u拆成两个节点u_in和u_out并在它们之间连接一条有向边(u_in, u_out)其容量等于该节点的容量。然后将所有原图中指向u的边改为指向u_in将所有原图中从u出发的边改为从u_out出发。这样所有经过节点u的流量都必须先流入u_in再通过那条容量受限的边流向u_out从而受到节点容量的限制。5.4 最小路径覆盖问题在一个有向无环图中求最少的路径数量使得这些路径覆盖图中所有顶点且每个顶点恰好被一条路径覆盖。建模方法将其转化为二分图最大匹配。将原图每个顶点i拆成两个点i作为左部和i作为右部。对于原图中的每条边(u, v)在二分图中添加边(u, v)。求出该二分图的最大匹配m。则最小路径覆盖数 原图顶点数 - 最大匹配数m。原理每个匹配边(u, v)相当于将路径...-u和路径v-...连接起来。初始时每个点自成一条路径共n条。每形成一个匹配就相当于将两条路径合并为一条路径数减少1。因此最大匹配意味着最大程度的路径合并从而得到最少的路径数。6. 进阶最小费用最大流问题现在我们来聊聊网络热词“最小费用最大流”。这其实是最大流问题的一个自然延伸。在之前的模型中我们只关心流量最大化。但在现实中通过不同的路径运输货物成本可能不同。我们不仅希望流量最大还希望总运输成本最低。6.1 问题定义与建模在最小费用最大流问题中每条边(u, v)除了容量c(u, v)外还有一个单位流量的费用cost(u, v)。表示每通过一个单位的流量需要花费的成本。我们的目标是在所有可能的最大流中找到一个总费用最小的流。网络的总费用定义为∑ f(u, v) * cost(u, v)对所有边求和。6.2 成功最短路径算法最常用的算法是Successive Shortest Path (SSP)算法或者其基于 Bellman-Ford 或 SPFA 的实现用于处理负权边因为反向边会引入负费用以及基于 Dijkstra 的优化版本需要处理负权常用 Johnson 算法思想或势能函数。算法思想基于SPFA初始流量为0。在残量网络中寻找从源点s到汇点t的单位费用最小的增广路径即路径上所有边单位费用之和最小。注意这里寻找的是“最短路径”但权重是费用。如果存在这样的路径就沿着这条路径增广尽可能多的流量受路径瓶颈容量限制。更新残量网络包括流量和反向边重复步骤2直到无法找到从s到t的路径即已达到最大流。为什么反向边费用为负这是算法的精妙之处。当我们沿边(u, v)推送了流量f我们创建的反向边(v, u)的容量为f但其费用设置为-cost(u, v)。这是因为如果之后我们通过反向边退回流量相当于撤销了之前在这条边上的运输那么之前产生的费用也应该被“退回”或“抵消”。这保证了算法能正确计算出全局最小费用。6.3 实现要点与复杂度基于 SPFA 的 SSP 算法实现起来相对直观但需要注意 SPFA 在最坏情况下的时间复杂度不理想。更稳定的实现是使用势能函数 Dijkstra的方法。势能函数为每个节点u维护一个势h[u]初始为0。每次用 Dijkstra 找最短路时将边(u, v)的权重从cost(u, v)调整为cost(u, v) h[u] - h[v]。可以证明这样调整后所有边权非负就可以使用更高效的 Dijkstra 算法。每次找到最短路并增广后更新势能h[u] dist[u]dist[u]是本次 Dijkstra 中从源点到u的最短距离。该算法的时间复杂度约为O(F * E log V)其中F是最大流值。对于流值较大的情况这可能较慢但对于许多实际问题已经足够。实操心得最小费用最大流是网络流建模的集大成者非常实用。例如在任务分配、资源调度、物流运输中它可以直接用来求解“在满足最大吞吐量下的最低成本方案”。在实现时建议先理解基于 SPFA 的版本再挑战势能Dijkstra 的优化版本。调试时可以从一个非常小的、能手工验证的样例开始仔细检查每次增广后每条边的流量、残量以及反向边的费用设置是否正确。7. 常见问题、调试技巧与实战建议即使理解了原理在亲手实现和应用时还是会遇到各种问题。这里分享一些我踩过的坑和总结的经验。7.1 常见错误与排查表问题现象可能原因排查方法程序陷入死循环或超时1. 寻找增广路的方式有误如DFS未处理反向边。2. 容量为0的边未正确跳过。3. 图存在负容量环在最小费用流中。1. 打印每次增广的路径和流量检查是否合理。2. 在BFS/DFS中严格检查cap 0才扩展。3. 对于最小费用流检查SPFA是否检测到负环。答案比预期小未达到最大流1. 反向边机制未实现或实现有误。2. 图的构建错误如边方向、容量设置错误。3. 源点/汇点设置错误。1.这是最常见错误确保正向边减流量时反向边加流量或加容量。2. 用一个小样例如一个简单的三条边路径手工模拟算法过程。3. 检查s和t的编号是否正确。答案比预期大几乎不可能除非流量累加逻辑出错。检查最大流值的累加代码确保只在找到有效增广路后才增加。最小费用流费用不正确1. 反向边的费用未设置为负值。2. 费用累加错误可能用了容量而非流量计算。3. 势能函数更新错误如果用了Dijkstra优化。1. 确认反向边(v, u)的费用是-cost(u, v)。2. 总费用增加应为bottleneck * (路径上所有边费用之和)。3. 在势能版本中确保每次 Dijkstra 前正确调整边权。7.2 调试技巧与小贴士构造微型测试用例不要一上来就用复杂数据。构造一个只有3-4个节点你一眼就能看出最大流应该是多少的图。手动模拟算法与程序输出对比。打印中间状态在每次增广后打印出当前流量、残量网络或者每条边的流量情况。这对于验证反向边是否正常工作特别有效。可视化工具如果问题复杂可以尝试用 Graphviz 等工具将你的图包括反向边画出来直观地看流量的分布。理解反向边的物理意义始终记住反向边的容量代表“可以退回的流量”。在残量网络中如果从u到v的正向边剩余容量是r从v到u的反向边剩余容量是f那么原边(u, v)上的当前流量就是f并且最多还能再流r。Dinic算法的当前弧优化实现 Dinic 时当前弧数组必须在每一轮 BFS 构建分层图后重置为每个节点的第一条边。但在同一轮 DFS 中它逐步后移并且不需要在 DFS 递归返回时回溯。7.3 工程实践与扩展思考在实际工程中比如芯片设计中的布线、交通流量分配、生产计划等网络流模型可能非常庞大。此时需要考虑效率可能需要更高效的算法如 Dinic, ISAP, Push-Relabel或启发式优化。建模灵活性实际问题往往带有更多约束如节点容量、带增益的流、有上下界的流等。需要熟练运用“拆点”、“超级源汇”、“构造循环流”等技巧将其转化为标准形式。近似解对于超大规模问题精确求解最大流可能计算代价过高可以考虑使用近似算法或基于流的启发式算法。网络流的世界远不止于此。上下界可行流、最小费用上下界流、最大权闭合子图、最大密度子图等问题都可以通过巧妙的构图规约到最大流或最小费用最大流模型来解决。掌握其核心思想和基本算法就相当于拥有了一把打开许多组合优化问题之门的钥匙。理解最大流和最小割不仅仅是学会两个算法更是学会了一种“网络”和“约束”的思维方式。当你再遇到资源分配、路径选择、切割分离这类问题时不妨想一想这能画成一张图吗能量化流动和约束吗如果能那么最大流最小割这把利器很可能就能为你提供一个清晰而优美的解决方案。
从水管网络到最大流最小割：核心概念、算法与应用全解析
1. 从水管网络到最大流一个接地气的开场干了这么多年算法和优化相关的工作我发现一个挺有意思的现象很多听起来高大上的概念比如“最大流”和“最小割”其实就藏在我们每天都能见到的生活场景里。想象一下你们小区的自来水供水系统或者更简单点你家里连接着花洒的那段水管网络。水源比如水塔或水泵就是起点你家花洒的出水口就是终点中间那些粗细不一、可能还有阀门控制的水管以及它们之间的连接点就构成了一张“网络图”。现在我问你在现有管道不爆管、阀门全开的情况下从水源到你家花洒单位时间内最多能流过来多少水这个“最大水流量”就是“最大流”问题最朴素的描述。那“最小割”又是什么咱们继续这个水管例子。假如有个调皮孩子想搞个恶作剧让你家停水但他力气有限每次只能切断几根水管。他的目标是让你家彻底没水同时希望自己切断的水管“总代价”最小——比如切断粗水管很费劲代价大切断细水管轻松些代价小。那么他应该切断哪几根水管才能用最小的“力气”达成停水的目的这个“需要切断的、代价最小的水管集合”就是“最小割”。最神奇的是在任何网络中最大流的值永远等于最小割的容量。这个听起来有点反直觉的结论就是著名的“最大流最小割定理”它是整个网络流理论的基石。这篇文章我就想用这种“说人话”的方式带你彻底搞懂这两个核心概念。无论你是正在啃《算法导论》的学生还是工作中偶尔需要处理资源调度、路径规划的工程师理解了这个框架很多问题都会豁然开朗。咱们不堆公式就用生活化的类比和一步步的推演把原理、算法和实际怎么用掰开揉碎了讲清楚。最后还会聊聊它的一个高级变种——“最小费用最大流”看看当流量“打车”要付“路费”时我们该如何精打细算。2. 核心概念拆解图、流与割在进入算法之前我们必须把几个最基础的定义像搭积木一样摆清楚。这些定义是后面所有推理和操作的“普通话”版本理解了它们你就读懂了网络流这门语言的字母表。2.1 网络图水管系统的地图首先我们得有一张“地图”。在网络流问题中这张地图叫做流网络本质上就是一个有向图。它包含以下几个要素节点就是地图上的点代表交叉路口、中转站。在我们水管模型里它就是水管之间的连接处、水泵、水塔、你家水表的位置。特别地我们规定其中一个是源点用s表示就是水源另一个是汇点用t表示就是最终的目的地比如你家花洒。有向边就是连接两个节点的、有方向的管道。从节点u指向节点v的边表示物质水、车、数据包可以从u流向v。边是单向的这很符合现实——水不能自己从低处往高处倒流除非有水泵但那可以建模为另一个节点和边。容量这是贴在每条边上的“标签”表示这条管道在单位时间内最多能允许通过多少“东西”。记作c(u, v)必须是非负实数。它就像水管的粗细或者公路的车道数。容量是边的固有属性是理论上的上限。这里有个关键点在基本的最大流问题中我们通常不允许有反向的边即如果存在(u, v)就不会有(v, u)或者即使有也视为两条独立的边。这是为了简化初始模型。后面我们会看到算法如何巧妙地“模拟”出反向流动。注意很多初学者会混淆“实际流量”和“容量”。容量是固定的、理论上的最大值就像水管的最大直径。而实际流量是我们需要计算和分配的、在容量限制下的一个动态值。2.2 什么是“流”规则比想象中严格现在我们要往这个水管网络里“注水”了。所谓的一个可行流就是给每条边分配一个流量值f(u, v)它必须满足三条非常合理且严格的“交通规则”容量限制对任意边(u, v)0 ≤ f(u, v) ≤ c(u, v)。这太好理解了流过一条边的流量不能超过它的容量也不能是负数基本模型中我们不允许倒流。流量守恒对于除了源点s和汇点t之外的任何一个中间节点流入这个节点的总流量必须等于流出这个节点的总流量。用公式表达就是∑f(u, i) ∑f(i, v)。这意味着水流在中间节点既不能无故产生也不能无故消失。所有从源点泵出的水最终都必须一滴不差地流到汇点中途没有损耗和囤积。这个规则是网络流合理性的核心保障。斜对称性这个规则在基础定义里有点“形式化”但它为后续算法提供了巨大便利。它规定f(u, v) -f(v, u)。意思是如果你认为从u到v流了 5 个单位那么从v到u的流量就记为 -5。在初始没有反向边的情况下f(v, u)通常就是 0。这个定义主要是为了数学上的统一在算法实现中它允许我们用“残量网络”中的反向边来记录“可以退回的流量”非常巧妙。一个可行流的总流量值|f|定义为从源点s净流出的流量也等于流入汇点t的净流量。最大流问题就是在所有可行流中找到那个总流量|f|最大的流。2.3 什么是“割”一把精准的手术刀“割”的概念比“流”要抽象一点但用“切断”来想就直观了。一个s-t割把整个网络图的节点分成两个不相交的集合S和T其中源点s在S里汇点t在T里。你可以想象用一把刀沿着节点之间的“缝隙”切下去把图切成左右两半s在左边 (S)t在右边 (T)。那么所有从左边S指向右边T的边就被这把刀“切断”了。这些被切断的边构成了这个割的割边集。这个割的容量定义为所有从S指向T的边的容量之和记作c(S, T) ∑ c(u, v)其中u∈S, v∈T。注意容量只关心从S到T的边不关心反方向的边从T到S。割的容量可以理解为“为了彻底断绝s和t之间的联系所需要切断的边的总理论最大通行能力”。那么最小割问题就是在所有可能的s-t割中找到那个容量c(S, T)最小的割。回到恶作剧孩子的例子最小割就是他切断水管“总粗细”总容量最小的那个方案。2.4 最大流最小割定理一个震撼的等式这是网络流理论中最优美、最重要的结论在任何流网络中从 s 到 t 的最大流值等于分隔 s 和 t 的所有割的最小容量。即max |f| min c(S, T)这个定理为什么重要它建立了“全局优化问题”最大流和“组合结构问题”最小割之间的等价桥梁。它告诉我们上界性任何流的流量都不可能超过任何一个割的容量。因为所有从s到t的流量必须穿过割边集而割边集的总容量是有限的。所以最大流 ≤ 最小割。可达性算法可以找到一个流和一个割使得流的流量等于割的容量。这就证明了等号可以成立因此最大流 最小割。在算法层面这意味着当我们用某种方法比如接下来要讲的Ford-Fulkerson方法求出了最大流的同时我们几乎可以“免费”地得到一个最小割。这个最小割就是算法结束后在“残量网络”中从源点s还能到达的节点集合S以及剩下的节点集合T。所有从S指向T的、且在原网络中容量已满即残量网络中对应边容量为0的边就构成了一个最小割集。这个特性在图像分割、网络可靠性分析等领域有直接应用。3. 核心算法解析Ford-Fulkerson 方法与 Edmonds-Karp 实现理解了概念我们来看怎么算。最经典、最直观的算法框架是Ford-Fulkerson 方法。它不是某一个具体算法而是一个思想框架“只要存在一条从源点到汇点的、每条边上都有剩余容量的路径称为增广路径我们就沿着这条路尽可能多地增加流量。”3.1 残量网络算法的舞台这是理解所有增广路算法的关键。对于当前的一个可行流f我们构造一个残量网络G_f。这个网络和原图有相同的节点但边和容量定义不同对于原图中的每条边(u, v)如果当前流量f(u, v) c(u, v)那么在残量网络中我们创建一条从u到v的正向边其剩余容量为c_f(u, v) c(u, v) - f(u, v)。这表示这条边还能再通过多少流量。同时我们创建一条从v到u的反向边其剩余容量为c_f(v, u) f(u, v)。这表示我们可以“退回”多少已分配的流量。反向边是算法能“反悔”、找到全局最优解的核心机制。一个生活化比喻把网络想象成一个单行道系统正向边但每开通一条单行道我们就同步修建一条平行的、仅供“掉头车”使用的应急车道反向边。应急车道的宽度等于当前单行道上的车流量。当我们发现另一条路更优时就可以让一部分车从应急车道掉头腾出空间给新的车流。反向边记录的正是这种“可退让”的潜力。3.2 增广路径与算法步骤在残量网络G_f中任何一条从s到t的、每条边剩余容量都大于0的路径就是一条增广路径。这条路径的“瓶颈”是路径上所有边剩余容量的最小值记作bottleneck。Ford-Fulkerson 方法的步骤可以概括为初始化所有边流量为0。在残量网络G_f中寻找一条从s到t的增广路径p。如果找不到算法结束当前流就是最大流。找到路径p的瓶颈容量bottleneck。对于路径p上的每一条边(u, v)如果它是正向边在原图中存在则增加其流量f(u, v) bottleneck。如果它是反向边对应原图中(v, u)的退回则减少原边的流量f(v, u) - bottleneck。这等价于在残量网络中正向边容量减少反向边容量增加。更新残量网络G_f返回步骤2。为什么反向边是灵魂看一个经典例子一个“X”形网络s连接A和BA和B都连接t同时s也直接连接t。如果不用反向边我们可能先找到路径 s-A-t把流量占满导致更优的全局方案 s-B-t 和 s-A-B-t 无法实现。有了反向边当我们后来找到路径 s-B-A-t 时可以通过A-t的反向边对应原图A-t的流量退回一部分流量转而从A流向B再流向t从而腾出s-A的容量给新的流量实现全局流量最大化。反向边提供了“重新路由”的可能性。3.3 Edmonds-Karp 算法用BFS保证效率基础的Ford-Fulkerson方法没有规定如何“寻找增广路径”。如果使用DFS随意寻找在最坏情况下比如容量是无理数算法可能永远不会终止或者效率极低复杂度与流量值有关不是多项式时间。Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个具体、高效的实现。它规定每次使用广度优先搜索在残量网络中寻找最短的增广路径即边数最少的路径。这一简单的策略带来了质的飞跃时间复杂度被证明为O(V * E^2)其中V是节点数E是边数。这是一个严格的多项式时间算法与边的容量大小无关。工作原理BFS 每次都找到边数最少的路径进行增广。这避免了 DFS 可能陷入的“长路径漩涡”能更快地扩大流量并且保证了算法在有限步内结束。实操心得在99%的编程竞赛和日常工程问题中当你需要实现最大流时Edmonds-KarpEK算法是首选的起点。它实现简单只需要BFS易于调试对于节点和边数在几百到几千规模的问题通常足够快。下面是一个高度简化的 EK 算法核心流程的伪代码描述帮助你理解其结构# 假设使用邻接表存储图每条边记录 (to, capacity, reverse_edge_index) def edmonds_karp(s, t): max_flow 0 while True: # 使用BFS寻找最短增广路径并记录路径上前驱节点和瓶颈值 queue [s] prev_node [-1] * N # 记录路径上前一个节点 prev_edge [-1] * N # 记录到达当前节点的边的索引 flow_to [0] * N # 记录到当前节点的路径上的最小剩余容量 flow_to[s] INF found False while queue and not found: u queue.pop(0) for i, (v, cap, rev) in enumerate(graph[u]): if cap 0 and prev_node[v] -1 and v ! s: # 有剩余容量且未访问 prev_node[v] u prev_edge[v] i flow_to[v] min(flow_to[u], cap) if v t: found True break queue.append(v) if not found: # 没有增广路了 break # 找到了增广路瓶颈值为 flow_to[t] bottleneck flow_to[t] max_flow bottleneck # 沿着路径更新残量网络 v t while v ! s: u prev_node[v] edge_idx prev_edge[v] # 减少正向边容量 graph[u][edge_idx].capacity - bottleneck # 增加反向边容量 (通过反向边索引找到) rev_edge_idx graph[u][edge_idx].rev graph[graph[u][edge_idx].to][rev_edge_idx].capacity bottleneck v u return max_flow注意事项在实现时存储反向边的技巧至关重要。通常我们在加边时同时加入正向边和反向边并互相记录对方的索引。这样在更新流量时可以O(1)地找到对应的反向边进行操作。这是实现中的关键细节容易出错。4. 算法实现细节与优化策略理解了 EK 算法的骨架我们深入到实现层面看看有哪些坑要避开以及如何让它跑得更快。4.1 数据结构的选择与边的存储网络流算法的性能与图的数据结构紧密相关。邻接矩阵在边非常稠密时可能简单但对于稀疏图大多数实际情况会浪费大量空间且寻找邻接边效率低。邻接表是绝对的主流选择。更具体地说我们通常使用“链式前向星”或“动态数组邻接表”来存储。每条边需要存储以下信息to: 边的终点。cap: 边的当前剩余容量注意是残量网络中的容量。flow: 当前流量有时可以不显式存储通过初始容量和当前容量推算。rev: 反向边在邻接表中的索引。这是实现的关键。加边的操作需要成对进行def add_edge(u, v, capacity): graph[u].append(Edge(tov, capcapacity, revlen(graph[v]))) graph[v].append(Edge(tou, cap0, revlen(graph[u])-1)) # 反向边初始容量为0初始化反向边容量为0符合初始流量为0的设定。当沿着正向边推送流量时减少其cap并增加对应反向边的cap这个反向边的cap就代表了可以退回的流量。4.2 寻找增广路径的BFS实现要点在 EK 算法中BFS 不仅要判断能否到达汇点t还必须记录路径以便回溯更新。通常我们用两个数组pre和pre_edge来实现pre[v]记录在 BFS 树中节点v是从哪个节点u访问过来的。pre_edge[v]记录是通过节点u的邻接表中的第几条边访问到v的。这样当 BFS 到达t后我们可以从t开始利用pre数组回溯到s同时用pre_edge找到具体是哪条边从而确定整条增广路径和瓶颈容量。一个常见的坑在 BFS 中判断条件必须是“边的剩余容量cap 0”才将其加入队列。这意味着我们只走还有“空间”的边。同时需要标记已访问节点防止走回头路和形成环路。4.3 Dinic 算法更强大的优化当图的规模更大节点/边数上万时EK 算法的O(V*E^2)复杂度可能显得吃力。Dinic 算法是更高效的选择平均表现和理论上限都更好时间复杂度为O(V^2 * E)对于单位容量图甚至能达到O(min(V^(2/3), E^(1/2)) * E)。Dinic 算法的核心思想是“分层图”“多路增广”BFS 构建分层图从源点s出发进行 BFS记录每个节点到s的最短距离层数。在残量网络中只保留从第i层指向第i1层的边。这保证了我们找到的路径都是最短的并且为后续 DFS 提供了清晰的指引。DFS 进行多路增广在分层图上进行 DFS寻找从s到t的路径。Dinic 的 DFS 是“阻塞流”式的它会尝试一次性找到多条增广路径并尽可能压榨每条路径的流量。DFS 过程中如果一个节点的出边已经无法推送更多流量就将其从当前分层图中临时移除称为“当前弧优化”避免后续 DFS 重复访问无效边。当前弧优化是 Dinic 算法的关键优化。在每次 DFS 中对每个节点维护一个指针指向下一条待尝试的边。当一条边被榨干剩余容量为0后指针就移动到下一条边。这样在整个算法过程中每条边最多被访问一次在构建阻塞流的那一轮 BFS-DFS 周期内极大地提高了效率。实操心得对于算法竞赛或高性能场景Dinic 是标配。它的实现比 EK 稍复杂但模板化程度很高。一旦掌握大部分网络流题目都能解决。它的性能优势在稀疏图、尤其是带有某种特征如二分图匹配转化来的流网络的图上非常明显。如果你发现 EK 算法超时升级到 Dinic 通常是第一选择。4.4 最小割的求解如前所述当最大流算法运行结束后在最终的残量网络G_f中从源点s出发只经过剩余容量cap 0的边所能到达的所有节点构成集合S。剩下的节点构成集合T。那么所有起点在S、终点在T、且在原网络中容量不为0的边就组成了一个最小割集。为什么这就是最小割因为算法结束后S和T之间所有边的剩余容量都为0这意味着这些边在原网络中的流量已经达到了满容量。根据最大流最小割定理这个割的容量正好等于最大流的值因此它必然是一个最小割。在代码实现上只需要在得到最大流后从s开始做一次 BFS 或 DFS只遍历cap 0的边就能标记出集合S。然后遍历原图的所有边如果一条边的起点在S终点不在S且原容量大于0那么这条边就在最小割集中。5. 从理论到应用经典问题建模实战最大流最小割不是空中楼阁它是一把强大的瑞士军刀可以巧妙解决许多看似不相关的组合优化问题。关键在于如何将实际问题“建模”成一个流网络。5.1 二分图最大匹配问题这是最经典的应用之一。问题描述有两组节点左集L和右集R中间有一些边连接左右节点。求一个最大的边集使得这个边集中的任意两条边都没有公共端点即每个节点最多被匹配一次。建模方法创建超级源点s用容量为1的边连接到左集L的每一个节点。创建超级汇点t用容量为1的边从右集R的每一个节点连接到t。将原有的左集到右集的边全部设置为容量为1的边。在这个新网络上跑最大流得到的最大流值就是最大匹配数。流量为1的边从L到R的边就对应了一组匹配。为什么有效容量为1的边保证了每个左节点最多流出一个单位流量匹配一条边每个右节点最多流入一个单位流量被匹配一次。从s到t的流自然就对应了一个合法的匹配方案。最大流即最大匹配。5.2 多源点多汇点问题有时不止一个起点或终点。例如一个城市有多个水库源点和多个居民区汇点问整个系统最大的供水总量。建模方法创建一个虚拟的超级源点S用容量为无穷大或该水源的实际最大供应量的边连接到所有真实源点。同样创建一个虚拟的超级汇点T用容量为无穷大或该居民区的最大需求的边从所有真实汇点连接到T。然后在新图上求从S到T的最大流即可。5.3 点容量问题在基本模型中容量限制在边上。但有时节点也有容量限制比如一个中转站每小时只能处理一定数量的货物。建模方法使用“拆点”技巧。将原节点u拆成两个节点u_in和u_out并在它们之间连接一条有向边(u_in, u_out)其容量等于该节点的容量。然后将所有原图中指向u的边改为指向u_in将所有原图中从u出发的边改为从u_out出发。这样所有经过节点u的流量都必须先流入u_in再通过那条容量受限的边流向u_out从而受到节点容量的限制。5.4 最小路径覆盖问题在一个有向无环图中求最少的路径数量使得这些路径覆盖图中所有顶点且每个顶点恰好被一条路径覆盖。建模方法将其转化为二分图最大匹配。将原图每个顶点i拆成两个点i作为左部和i作为右部。对于原图中的每条边(u, v)在二分图中添加边(u, v)。求出该二分图的最大匹配m。则最小路径覆盖数 原图顶点数 - 最大匹配数m。原理每个匹配边(u, v)相当于将路径...-u和路径v-...连接起来。初始时每个点自成一条路径共n条。每形成一个匹配就相当于将两条路径合并为一条路径数减少1。因此最大匹配意味着最大程度的路径合并从而得到最少的路径数。6. 进阶最小费用最大流问题现在我们来聊聊网络热词“最小费用最大流”。这其实是最大流问题的一个自然延伸。在之前的模型中我们只关心流量最大化。但在现实中通过不同的路径运输货物成本可能不同。我们不仅希望流量最大还希望总运输成本最低。6.1 问题定义与建模在最小费用最大流问题中每条边(u, v)除了容量c(u, v)外还有一个单位流量的费用cost(u, v)。表示每通过一个单位的流量需要花费的成本。我们的目标是在所有可能的最大流中找到一个总费用最小的流。网络的总费用定义为∑ f(u, v) * cost(u, v)对所有边求和。6.2 成功最短路径算法最常用的算法是Successive Shortest Path (SSP)算法或者其基于 Bellman-Ford 或 SPFA 的实现用于处理负权边因为反向边会引入负费用以及基于 Dijkstra 的优化版本需要处理负权常用 Johnson 算法思想或势能函数。算法思想基于SPFA初始流量为0。在残量网络中寻找从源点s到汇点t的单位费用最小的增广路径即路径上所有边单位费用之和最小。注意这里寻找的是“最短路径”但权重是费用。如果存在这样的路径就沿着这条路径增广尽可能多的流量受路径瓶颈容量限制。更新残量网络包括流量和反向边重复步骤2直到无法找到从s到t的路径即已达到最大流。为什么反向边费用为负这是算法的精妙之处。当我们沿边(u, v)推送了流量f我们创建的反向边(v, u)的容量为f但其费用设置为-cost(u, v)。这是因为如果之后我们通过反向边退回流量相当于撤销了之前在这条边上的运输那么之前产生的费用也应该被“退回”或“抵消”。这保证了算法能正确计算出全局最小费用。6.3 实现要点与复杂度基于 SPFA 的 SSP 算法实现起来相对直观但需要注意 SPFA 在最坏情况下的时间复杂度不理想。更稳定的实现是使用势能函数 Dijkstra的方法。势能函数为每个节点u维护一个势h[u]初始为0。每次用 Dijkstra 找最短路时将边(u, v)的权重从cost(u, v)调整为cost(u, v) h[u] - h[v]。可以证明这样调整后所有边权非负就可以使用更高效的 Dijkstra 算法。每次找到最短路并增广后更新势能h[u] dist[u]dist[u]是本次 Dijkstra 中从源点到u的最短距离。该算法的时间复杂度约为O(F * E log V)其中F是最大流值。对于流值较大的情况这可能较慢但对于许多实际问题已经足够。实操心得最小费用最大流是网络流建模的集大成者非常实用。例如在任务分配、资源调度、物流运输中它可以直接用来求解“在满足最大吞吐量下的最低成本方案”。在实现时建议先理解基于 SPFA 的版本再挑战势能Dijkstra 的优化版本。调试时可以从一个非常小的、能手工验证的样例开始仔细检查每次增广后每条边的流量、残量以及反向边的费用设置是否正确。7. 常见问题、调试技巧与实战建议即使理解了原理在亲手实现和应用时还是会遇到各种问题。这里分享一些我踩过的坑和总结的经验。7.1 常见错误与排查表问题现象可能原因排查方法程序陷入死循环或超时1. 寻找增广路的方式有误如DFS未处理反向边。2. 容量为0的边未正确跳过。3. 图存在负容量环在最小费用流中。1. 打印每次增广的路径和流量检查是否合理。2. 在BFS/DFS中严格检查cap 0才扩展。3. 对于最小费用流检查SPFA是否检测到负环。答案比预期小未达到最大流1. 反向边机制未实现或实现有误。2. 图的构建错误如边方向、容量设置错误。3. 源点/汇点设置错误。1.这是最常见错误确保正向边减流量时反向边加流量或加容量。2. 用一个小样例如一个简单的三条边路径手工模拟算法过程。3. 检查s和t的编号是否正确。答案比预期大几乎不可能除非流量累加逻辑出错。检查最大流值的累加代码确保只在找到有效增广路后才增加。最小费用流费用不正确1. 反向边的费用未设置为负值。2. 费用累加错误可能用了容量而非流量计算。3. 势能函数更新错误如果用了Dijkstra优化。1. 确认反向边(v, u)的费用是-cost(u, v)。2. 总费用增加应为bottleneck * (路径上所有边费用之和)。3. 在势能版本中确保每次 Dijkstra 前正确调整边权。7.2 调试技巧与小贴士构造微型测试用例不要一上来就用复杂数据。构造一个只有3-4个节点你一眼就能看出最大流应该是多少的图。手动模拟算法与程序输出对比。打印中间状态在每次增广后打印出当前流量、残量网络或者每条边的流量情况。这对于验证反向边是否正常工作特别有效。可视化工具如果问题复杂可以尝试用 Graphviz 等工具将你的图包括反向边画出来直观地看流量的分布。理解反向边的物理意义始终记住反向边的容量代表“可以退回的流量”。在残量网络中如果从u到v的正向边剩余容量是r从v到u的反向边剩余容量是f那么原边(u, v)上的当前流量就是f并且最多还能再流r。Dinic算法的当前弧优化实现 Dinic 时当前弧数组必须在每一轮 BFS 构建分层图后重置为每个节点的第一条边。但在同一轮 DFS 中它逐步后移并且不需要在 DFS 递归返回时回溯。7.3 工程实践与扩展思考在实际工程中比如芯片设计中的布线、交通流量分配、生产计划等网络流模型可能非常庞大。此时需要考虑效率可能需要更高效的算法如 Dinic, ISAP, Push-Relabel或启发式优化。建模灵活性实际问题往往带有更多约束如节点容量、带增益的流、有上下界的流等。需要熟练运用“拆点”、“超级源汇”、“构造循环流”等技巧将其转化为标准形式。近似解对于超大规模问题精确求解最大流可能计算代价过高可以考虑使用近似算法或基于流的启发式算法。网络流的世界远不止于此。上下界可行流、最小费用上下界流、最大权闭合子图、最大密度子图等问题都可以通过巧妙的构图规约到最大流或最小费用最大流模型来解决。掌握其核心思想和基本算法就相当于拥有了一把打开许多组合优化问题之门的钥匙。理解最大流和最小割不仅仅是学会两个算法更是学会了一种“网络”和“约束”的思维方式。当你再遇到资源分配、路径选择、切割分离这类问题时不妨想一想这能画成一张图吗能量化流动和约束吗如果能那么最大流最小割这把利器很可能就能为你提供一个清晰而优美的解决方案。
