# 网络流算法Push-relabel的Python实现

```__author__ = 'xanxus'
nodeNum, edgeNum = 0, 0
arcs = []

class Arc(object):
def __init__(self):
self.src = -1
self.dst = -1
self.cap = -1

s, t = -1, -1
with open('sample.dimacs') as f:
line = line.strip()
if line.startswith('p'):
tokens = line.split(' ')
nodeNum = int(tokens[2])
edgeNum = tokens[3]
if line.startswith('n'):
tokens = line.split(' ')
if tokens[2] == 's':
s = int(tokens[1])
if tokens[2] == 't':
t = int(tokens[1])
if line.startswith('a'):
tokens = line.split(' ')
arc = Arc()
arc.src = int(tokens[1])
arc.dst = int(tokens[2])
arc.cap = int(tokens[3])
arcs.append(arc)

nodes = [-1] * nodeNum
for i in range(s, t + 1):
nodes[i - s] = i
adjacent_matrix = [[0 for i in range(nodeNum)] for j in range(nodeNum)]
forward_matrix = [[0 for i in range(nodeNum)] for j in range(nodeNum)]
for arc in arcs:
adjacent_matrix[arc.src - s][arc.dst - s] = arc.cap
forward_matrix[arc.src - s][arc.dst - s] = arc.cap
flow_matrix = [[0 for i in range(nodeNum)] for j in range(nodeNum)]

height = [0] * nodeNum
height[0] = nodeNum

def excess(v):
in_flow, out_flow = 0, 0
for i in range(len(flow_matrix)):
in_flow += flow_matrix[i][v]
out_flow += flow_matrix[v][i]
return in_flow - out_flow

def exist_excess():
for v in range(len(flow_matrix)):
if excess(v) > 0 and v != t - s:
return v
return None

v = exist_excess()
while v:
has_lower_height = False
if adjacent_matrix[v][j] != 0 and height[v] > height[j]:
has_lower_height = True
if forward_matrix[v][j] != 0:
flow_matrix[v][j] += bottleneck
else:
bottleneck = min([excess(v), flow_matrix[j][v]])
flow_matrix[j][v] -= bottleneck
if not has_lower_height:
height[v] += 1
v = exist_excess()
for arc in arcs:
print 'f %d %d %d' % (arc.src, arc.dst, flow_matrix[arc.src - s][arc.dst - s])```

104 篇文章41 人订阅

0 条评论

## 相关文章

714190

18940

### 矩阵快速幂小结

矩阵快速幂大概是用来解决这样一类问题，当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办？ ...

33150

1.1K100

55530

30880

7520

17920

319110

### 深海中的STL—mt19937

mt19937 当你第一眼看到这玩意儿的时候 肯定禁不住吐槽：纳尼？这是什么鬼？ 确实，这个东西鲜为人知，但是它却有着卓越的性能 简介 mt19937是c++1...

32540