网络流学习笔记（基础）

王树森教程

基础概念

流网络（Flow Network）：有向图$G=(V,E)$，每条边$(u,v)\in E$有容量 $c(u,v)\ge 0$，约定：若 $(u,v)\notin E$，则 $c(u,v)=0$

可行流（Feasible Flow）：满足以下条件的流函数 $f:V\times V\to \mathbb{R}$：，容量限制：$0\le f(u,v)\le c(u,v)$，流量守恒：对任意 $u\ne s,t$，有
${\sum }_{v\in V}f(v,u)={\sum }_{v\in V}f(u,v)$

最大流问题：寻找从源点 $s$到汇点 $t $的可行流，使得流量$|f| = \sum_{v \in V} f(s, v)$最大化

层次图（Level Graph）：从源点 $s$出发进行 BFS，记录每个节点的层次$level[u]$（即 $s$到 $u$的最短距离）

阻塞流（Blocking Flow）：在层次图中无法再找到从 $s$ 到$ t $的路径时的流，不一定是最大流，但能保证每一步有效推进

---

核心算法

1. Ford-Fulkerson 方法

核心思想：通过残留网络寻找增广路径
步骤：

1. 初始化残留网络 $G_f$（初始时$G_f=G$）
2. 在 $G_f$中寻找一条$s\to t$的路径（增广路径）
3. 计算路径上的最小残留容量 Δ = min ⁡ { c f ( u , v ) } \Delta = \min\{c_f(u, v)\} Δ=min{cf​(u,v)}
4. 沿路径增加流量 $\Delta$，更新残留网络
5. 重复直到没有增广路径

2. Edmonds-Karp 算法

改进点：使用 BFS 寻找最短增广路径

def edmonds_karp(graph, s, t):# 初始化残留网络和流量max_flow = 0while True:# BFS 寻找增广路径parent = bfs(residual_graph, s, t)if not parent[t]: break# 计算最小残留容量delta = INFv = twhile v != s:u = parent[v]delta = min(delta, residual_graph[u][v])v = u# 更新残留网络v = twhile v != s:u = parent[v]residual_graph[u][v] -= deltaresidual_graph[v][u] += deltav = umax_flow += deltareturn max_flow

3. Dinic 算法

优化策略：

1. 分层图（Level Graph）：BFS 构建层次结构
2. 阻塞流（Blocking Flow）：DFS 多路增广

三阶段循环：

1. BFS 构建层次图（Level Graph）
2. DFS 寻找阻塞流（Blocking Flow）
3. 更新残留网络并累加流量

数据结构设计

class Edge:def __init__(self, to, rev, capacity):self.to = to    # 指向的节点self.rev = rev  # 反向边在邻接表中的索引self.cap = capacity  # 剩余容量class Dinic:def __init__(self, n):self.size = nself.graph = [[] for _ in range(n)]  # 邻接表存储def add_edge(self, fr, to, cap):# 正向边forward = Edge(to, len(self.graph[to]), cap)# 反向边（初始容量0）backward = Edge(fr, len(self.graph[fr]), 0)self.graph[fr].append(forward)self.graph[to].append(backward)

分层图构建（BFS）

def bfs_level(self, s, t):level = [-1] * self.sizequeue = deque()level[s] = 0queue.append(s)while queue:u = queue.popleft()for edge in self.graph[u]:if edge.cap > 0 and level[edge.to] == -1:level[edge.to] = level[u] + 1queue.append(edge.to)if edge.to == t:return level  # 提前终止优化return level

阻塞流寻找（DFS with Optimization）

def dfs_flow(self, u, t, upTo, iter_, level):if u == t:return upTofor i in range(iter_[u], len(self.graph[u])):iter_[u] = i  # 当前弧优化edge = self.graph[u][i]if edge.cap > 0 and level[u] < level[edge.to]:d = self.dfs_flow(edge.to, t, min(upTo, edge.cap), iter_, level)if d > 0:edge.cap -= dself.graph[edge.to][edge.rev].cap += dreturn dreturn 0

主算法流程

def max_flow(self, s, t):flow = 0while True:level = self.bfs_level(s, t)if level[t] == -1:  # 无法到达汇点return flowiter_ = [0] * self.size  # 当前弧数组while True:f = self.dfs_flow(s, t, float('inf'), iter_, level)if f == 0:breakflow += f

---

最大流最小割定理

割（Cut）：将顶点分为 $S$ 和$T$，其中$s\in S,t\in T$

割的容量：$c(S,T)={\sum }_{u\in S,v\in T}c(u,v)$

定理：最大流值 = 最小割容量