Index
Help
1
25
2
25
3
4
5
6
7
8
9
10
11
12
-100
13
14
15
16
17
18
19
20
25
21
22
23
25
24
25
26
27
28
29
30
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
0
20
0
21
0
22
0
23
0
24
0
25
0
26
0
27
0
28
0
29
0
30
0
def
AdmissibleEdge(v,eps):
for
w
in
Neighborhood(v):
if
ReducedCosts((v,w)) < 0:
return
(v,w)
return
None
def
ReducedCosts((u,v)):
return
cost[(u,v)] + pot[u] - pot[v]
eps = RecalculateCosts()# for integer eps
while
eps > 1:
for
e
in
Edges():
if
ReducedCosts(e) > 0:
flow[e] = 0
elif
ReducedCosts(e) < 0:
flow[e] = cap(e)
IsFlow = False
while
not
IsFlow:
v = ActiveVertex()
if
v:
e = AdmissibleEdge(v,eps)
if
e:
delta = Min(res(e),excess(v))
if
ForwardEdge(e[0],e[1]):
flow[(e[0],e[1])] = flow[(e[0],e[1])] + delta
else
:
flow[(e[1],e[0])] = flow[(e[1],e[0])] - delta
else
:
Lower(v,eps / 2)
else
:
IsFlow = True
eps = eps / 2