最大流问题（Dinic算法）

题目描述
给定一个有向图G=(V,E)，其中每条边(u,v)∈E有一个非负容量c(u,v)≥0。指定源点s和汇点t，求从s到t的最大流量。Dinic算法是一种高效的最大流算法，特别适合稠密图，时间复杂度为O(V²E)。

算法步骤详解

1. 基本概念建立

• 剩余网络：对于当前流量f，剩余容量r(u,v)=c(u,v)-f(u,v)+f(v,u)
• 层次图：从源点s出发，通过BFS给每个顶点标记层次（距离）
• 阻塞流：在层次图中无法再推送更多流量的流

2. 算法框架
Dinic算法采用分层思想，迭代执行以下步骤：

1. 构建层次图
2. 在层次图中寻找阻塞流
3. 将阻塞流加入总流量
4. 重复直到无法构建从s到t的层次图

3. 构建层次图（BFS阶段）

def BFS_level_graph(G, s, t):
    level = [-1] * len(V)  # 初始化所有顶点层次为-1
    queue = deque()
    level[s] = 0
    queue.append(s)
    
    while queue:
        u = queue.popleft()
        for v in range(len(V)):
            # 如果边(u,v)有剩余容量且v未被访问
            if r[u][v] > 0 and level[v] == -1:
                level[v] = level[u] + 1
                queue.append(v)
    return level[t] != -1  # 返回是否能到达汇点t

4. 寻找阻塞流（DFS阶段）

def DFS_blocking_flow(u, flow, t, level, ptr):
    if u == t:
        return flow
        
    for i in range(ptr[u], len(V)):
        v = i
        ptr[u] = i  # 当前弧优化，避免重复检查无效边
        
        # 只在层次递增的边上推送流量
        if level[v] == level[u] + 1 and r[u][v] > 0:
            pushed = DFS_blocking_flow(v, min(flow, r[u][v]), t, level, ptr)
            if pushed > 0:
                r[u][v] -= pushed  # 更新正向边剩余容量
                r[v][u] += pushed  # 更新反向边剩余容量
                return pushed
    return 0

5. 主算法流程

def dinic_algorithm(G, s, t):
    max_flow = 0
    n = len(V)
    r = [[0]*n for _ in range(n)]  # 剩余容量矩阵
    
    # 初始化剩余网络
    for u in range(n):
        for v in range(n):
            r[u][v] = G[u][v]  # 初始剩余容量等于原始容量
    
    while BFS_level_graph(G, s, t):  # 当存在增广路径时
        ptr = [0] * n  # 当前弧指针数组
        while True:
            flow = DFS_blocking_flow(s, float('inf'), t, level, ptr)
            if flow == 0:
                break
            max_flow += flow
    
    return max_flow

6. 关键优化技术

当前弧优化

• 维护指针数组ptr，记录每个顶点已检查的边
• 避免重复检查不可能推送流量的边
• 显著减少DFS的递归调用次数

层次图构建

• 确保每次增广都沿着最短路径
• 避免DFS陷入长路径的无效搜索
• 保证算法在多项式时间内完成

7. 复杂度分析

• 时间复杂度：O(V²E)
• 空间复杂度：O(V+E)
• 对于单位容量图：O(E√E)或O(E√V)
• 对于二分图匹配：O(E√V)

8. 算法正确性证明

• 层次图确保每次增广都沿着最短路径
• 阻塞流保证无法在当前层次图中找到更多流量
• 当无法构建s到t的层次图时，当前流即为最大流

9. 实际应用示例
考虑一个6顶点网络：

s→1: 10    s→2: 10
1→3: 25    1→2: 2
2→4: 15    3→t: 10
4→t: 10    3→4: 6

Dinic算法执行过程：

1. 第一次BFS：层次[s:0, 1:1, 2:1, 3:2, 4:2, t:3]
2. 推送阻塞流：s→1→3→t:10, s→2→4→t:10
3. 第二次BFS：更新剩余网络，继续寻找阻塞流
4. 最终得到最大流：20

该算法通过分层和阻塞流的组合，高效解决了最大流问题，在实践中表现优异。