流网络边容量减1后的最大流O(|E|+|V|)时间算法设计与分析

给定整数容量的流网络 ( G=(V, E) )，取任意边 ( e \in E )，构造流网络 ( G' )：( G' ) 与 ( G ) 结构完全一致，仅边 ( e ) 的容量比 ( G ) 中对应值小1。已知 ( G ) 的整数最大流 ( f )，请设计一个时间复杂度为 ( O(|E| + |V|) ) 的算法，计算 ( G' ) 的整数最大流 ( f' )。

1. 快速判断是否无需调整最大流 #

先检查原最大流 ( f ) 中边 ( e=(u,v) ) 的流量 ( f(e) )：

• 如果 ( f(e) < c_G(e) )（( c_G(e) ) 是 ( G ) 中 ( e ) 的容量）：
  降低 ( e ) 的容量1后，新容量 ( c_{G'}(e) = c_G(e)-1 ) 仍然大于等于 ( f(e) )，原最大流 ( f ) 在 ( G' ) 中依然是可行流，同时也是最大流（因为原流已是 ( G ) 的最大流，( G' ) 的容量不超过 ( G )，所以 ( f ) 不可能再增大）。此时直接返回 ( f' = f )，算法结束。
• 如果 ( f(e) = c_G(e) )：
  原流 ( f ) 在 ( G' ) 中不可行（因为 ( f(e) > c_{G'}(e) )），需要进一步处理。

2. 调整残差图并寻找流量补偿路径 #

当 ( f(e) = c_G(e) ) 时，基于原流的残差图做如下调整：

1. 修正残差容量：
   • 原残差图中，( e=(u,v) ) 的正向残差容量为 ( c_G(e)-f(e)=0 )，反向边 ( (v,u) ) 的残差容量为 ( f(e)=c_G(e) )。
   • 对应 ( G' ) 的残差图，将反向边 ( (v,u) ) 的残差容量改为 ( c_G(e)-1 )（相当于需要“退回”1单位流量），正向边 ( (u,v) ) 的残差容量保持0。
2. 寻找反向增广路：
   在调整后的残差图中，从汇点 ( t ) 出发，用BFS或DFS遍历，寻找一条到源点 ( s ) 的路径。这条路径的作用是：把原流中多出来的1单位流量（因为 ( e ) 容量降了1）从 ( t ) 反向送回 ( s )，抵消 ( e ) 上的流量溢出。
3. 确定最终最大流：
   • 如果找到这条路径：沿着路径调整流量（每经过一条边就增减对应残差容量的1单位流量），调整后的流是 ( G' ) 的可行流，且流量仍为 ( f )，因此 ( f' = f )。
   • 如果找不到这条路径：说明无法通过其他边的流量调整来补偿 ( e ) 容量降低的影响，此时 ( G' ) 的最大流只能是 ( f-1 )。

• 第一步的判断是 ( O(1) ) 操作，仅需对比 ( f(e) ) 和 ( c_G(e) )。
• 第二步中，残差图的调整是 ( O(1) ) 操作，仅修改两条边的容量；BFS/DFS遍历残差图的时间复杂度为 ( O(|E| + |V|) )，这是算法的时间瓶颈。
• 综上，整个算法的时间复杂度为 ( O(|E| + |V|) )，满足题目要求。

内容的提问来源于stack exchange，提问作者Hope Karpov