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
|