网络流学习笔记（基础）

王树森教程

基础概念

流网络（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 = 0
    while True:
        # BFS 寻找增广路径
        parent = bfs(residual_graph, s, t)
        if not parent[t]: break
        # 计算最小残留容量
        delta = INF
        v = t
        while v != s:
            u = parent[v]
            delta = min(delta, residual_graph[u][v])
            v = u
        # 更新残留网络
        v = t
        while v != s:
            u = parent[v]
            residual_graph[u][v] -= delta
            residual_graph[v][u] += delta
            v = u
        max_flow += delta
    return 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 = n
        self.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.size
    queue = deque()
    level[s] = 0
    queue.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] + 1
                queue.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 upTo
    for 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 -= d
                self.graph[edge.to][edge.rev].cap += d
                return d
    return 0

主算法流程

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

最大流最小割定理

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

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

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