最大流预留推进算法的python程序,要求输出每次迭代时的通行能力最小的点以及每次迭代时的增广路以及对应的容量,最后输出这个最大流
时间: 2024-03-10 16:47:39 浏览: 47
以下是一个基于预流推进算法的Python程序,用于解决最大流问题,同时输出每次迭代时的通行能力最小的点以及每次迭代时的增广路以及对应的容量:
```python
from queue import Queue
INF = float('inf')
class Edge:
def __init__(self, v, u, c):
self.v = v # 起点
self.u = u # 终点
self.c = c # 容量
class Vertex:
def __init__(self):
self.h = 0 # 高度
self.e = 0 # 超额流量
def bfs(graph, s, t):
n = len(graph)
level = [-1] * n
level[s] = 0
q = Queue()
q.put(s)
while not q.empty():
u = q.get()
for v, c in graph[u].items():
if level[v] == -1 and c > 0:
level[v] = level[u] + 1
q.put(v)
return level[t] != -1, level
def push(graph, u, v, e, vertex):
f = min(e, graph[u][v])
graph[u][v] -= f
graph[v][u] += f
vertex[u].e -= f
vertex[v].e += f
return f
def relabel(graph, u, vertex):
min_h = INF
for v, c in graph[u].items():
if c > 0:
min_h = min(min_h, vertex[v].h)
vertex[u].h = min_h + 1
def discharge(graph, u, vertex):
while vertex[u].e > 0:
for v, c in graph[u].items():
if c > 0 and vertex[u].h == vertex[v].h + 1:
push(graph, u, v, vertex[u].e, vertex)
if vertex[u].e == 0:
break
if vertex[u].e > 0:
relabel(graph, u, vertex)
def max_flow(graph, s, t):
n = len(graph)
vertex = [Vertex() for _ in range(n)]
vertex[s].h = n
for v, c in graph[s].items():
push(graph, s, v, c, vertex)
while True:
u = -1
for i in range(n):
if vertex[i].e > 0:
if u == -1 or vertex[i].h > vertex[u].h:
u = i
if u == -1:
break
old_h = vertex[u].h
discharge(graph, u, vertex)
if vertex[u].h > old_h:
vertex.insert(0, vertex.pop(u))
max_flow = sum(graph[s].values())
path = [(s, t, max_flow)]
while max_flow > 0:
p = []
f = INF
u = s
while u != t:
for v, c in graph[u].items():
if c > 0 and vertex[u].h == vertex[v].h + 1:
f = min(f, c)
p.append((u, v, f))
u = v
break
else:
h = min(vertex[v].h for v, c in graph[u].items() if c > 0)
relabel(graph, u, vertex)
if vertex[u].h >= n:
return '无法计算最大流'
for e in p:
push(graph, e[0], e[1], e[2], vertex)
max_flow -= f
path.append((p, f))
return path[:-1]
if __name__ == '__main__':
graph = {
0: {1: 16, 2: 13},
1: {2: 10, 3: 12},
2: {1: 4, 4: 14},
3: {2: 9, 5: 20},
4: {3: 7, 5: 4},
5: {}
}
path = max_flow(graph, 0, 5)
max_flow = sum(graph[0].values())
print(f'最大流为{max_flow}')
for p, f in path:
if type(p) == tuple:
print(f'通行能力最小的点为{p}')
else:
print(f'增广路为{p},容量为{f}')
```
该程序定义了 `Edge` 和 `Vertex` 两个类来表示边和顶点,`bfs` 函数实现了广度优先搜索来构建层数,`push` 函数和 `relabel` 函数分别实现了推送操作和 relabel 操作,`discharge` 函数递归地调用 `push` 函数和 `relabel` 函数来找到增广路,并实现了预流推进算法的主要逻辑,`max_flow` 函数通过预流推进算法来计算最大流,并返回增广路以及对应的容量,`main` 函数中定义了一个图,并调用 `max_flow` 函数来计算最大流。
以上代码仅供参考,实际实现可能需要根据具体情况进行调整。