62 lines
2.2 KiB
Python
62 lines
2.2 KiB
Python
from collections import deque
|
||
|
||
|
||
class MaxFlow:
|
||
def __init__(self, vertices):
|
||
self.V = vertices # 图的顶点数
|
||
self.graph = [[] for _ in range(vertices)] # 邻接表表示图
|
||
self.level = [-1] * vertices # 层次标记
|
||
self.ptr = [0] * vertices # 每个节点在其邻接边中的指针
|
||
|
||
def add_edge(self, u, v, capacity):
|
||
"""添加从u到v的边，并反向边的容量初始化为0"""
|
||
self.graph[u].append([v, capacity, len(self.graph[v])]) # (目标点, 容量, 反向边的索引)
|
||
self.graph[v].append([u, 0, len(self.graph[u]) - 1]) # (源点, 容量0, 反向边的索引)
|
||
|
||
def bfs(self, source, sink):
|
||
"""BFS进行分层图构建"""
|
||
queue = deque([source])
|
||
self.level = [-1] * self.V
|
||
self.level[source] = 0
|
||
|
||
while queue:
|
||
u = queue.popleft()
|
||
|
||
for v, cap, _ in self.graph[u]:
|
||
if self.level[v] == -1 and cap > 0: # 未访问且容量大于0
|
||
self.level[v] = self.level[u] + 1
|
||
if v == sink:
|
||
return True
|
||
queue.append(v)
|
||
|
||
return False
|
||
|
||
def dfs(self, u, sink, flow):
|
||
"""DFS寻找增广路径并更新残余图"""
|
||
if u == sink:
|
||
return flow
|
||
while self.ptr[u] < len(self.graph[u]):
|
||
v, cap, rev = self.graph[u][self.ptr[u]]
|
||
if self.level[v] == self.level[u] + 1 and cap > 0:
|
||
current_flow = min(flow, cap)
|
||
result = self.dfs(v, sink, current_flow)
|
||
if result > 0:
|
||
# 更新正向边和反向边
|
||
self.graph[u][self.ptr[u]][1] -= result
|
||
self.graph[v][rev][1] += result
|
||
return result
|
||
self.ptr[u] += 1
|
||
return 0
|
||
|
||
def dinic(self, source, sink):
|
||
"""Dinic算法计算最大流"""
|
||
max_flow = 0
|
||
while self.bfs(source, sink):
|
||
self.ptr = [0] * self.V
|
||
while True:
|
||
flow = self.dfs(source, sink, float('Inf'))
|
||
if flow == 0:
|
||
break
|
||
max_flow += flow
|
||
return max_flow
|