最大流基础

图

说明

不断在残量网络找增广路并增加流量；下例 Edmonds–Karp 使用 BFS。

分析

残量网络记录一条边还能增加多少流，也记录沿反向边撤回已有流的能力。BFS 找到一条增广路后，取路上的最小剩余容量作为本次增量，并同步更新正反边。

图解推演

正文网络可沿 0→1→3 送 2、0→2→3 送 2，随后沿 0→1→2→3 再送 1，总流量 5。源点总出容量也是 5，给出匹配的上界。每次送流同时增加反向残量，才能在后续增广中撤回旧选择；反向边不是额外产生流。

查看图表代码

适用前提与边界

容量必须是方形的非负整数矩阵，源点 s 与汇点 t 必须是矩阵内的合法编号且 s≠t，累计流量不能超出 int 范围。反复执行到找不到增广路即得到最大流；示例会修改传入的容量矩阵。不要传入 s=t：例如单点矩阵 [[0]] 会让本实现的路径检查立即成功，却没有边可增广，外层循环无法结束。

示例输入与调用

capacity := [][]int{{0, 3, 2, 0}, {0, 0, 1, 2}, {0, 0, 0, 3}, {0, 0, 0, 0}}
	fmt.Println(MaxFlow(capacity, 0, 3))

运行输出

5

完整 Go 示例

package main

import "fmt"

func MaxFlow(capacity [][]int, s, t int) int {
	n := len(capacity)
	flow := 0
	for {
		parent := make([]int, n)
		for i := range parent {
			parent[i] = -1
		}
		parent[s] = s
		q := []int{s}
		for h := 0; h < len(q) && parent[t] < 0; h++ {
			u := q[h]
			for v, c := range capacity[u] {
				if parent[v] < 0 && c > 0 {
					parent[v] = u
					q = append(q, v)
				}
			}
		}
		if parent[t] < 0 {
			break
		}
		add := int(^uint(0) >> 1)
		for v := t; v != s; v = parent[v] {
			if capacity[parent[v]][v] < add {
				add = capacity[parent[v]][v]
			}
		}
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			capacity[u][v] -= add
			capacity[v][u] += add
		}
		flow += add
	}
	return flow
}

func main() {
	capacity := [][]int{{0, 3, 2, 0}, {0, 0, 1, 2}, {0, 0, 0, 3}, {0, 0, 0, 0}}
	fmt.Println(MaxFlow(capacity, 0, 3))
}