最大ストリームアルゴリズム
32631 ワード
プリフロー推進アルゴリズム(push-relable),時間複雑度O(V^2 E)
1
//
The push-relable algorithm code due to CLRS chapter 26
2
#include
<
iostream
>
3
#include
<
list
>
4
using
namespace
std;
5
const
int
N
=
100
;
6
int
n;
//
vertex number
7
int
e[N];
//
residual flow of the vertex
8
int
h[N];
//
height of the vertex
9
int
c[N][N];
//
capacity of the edge
10
int
f[N][N];
//
flow of the edge
11
list
<
int
>
ev;
//
excess flow vertex
12
list
<
int
>
edge[N];
//
edge link list
13
bool
flag[N];
//
lable whether the vertex is in the flow list
14
15
inline
void
Push(
int
u,
int
v)
//
push flow from edge (u, v)
16
{
17
int
df
=
min(e[u], c[u][v]
-
f[u][v]);
18
f[u][v]
+=
df;
19
f[v][u]
=
-
f[u][v];
20
e[u]
-=
df;
21
e[v]
+=
df;
22
}
23
24
void
Relable(
int
u)
//
re-lable heght of vertex u
25
{
26
h[u]
=
n
*
2
-
1
;
27
for
(list
<
int
>
::iterator iter
=
edge[u].begin(); iter
!=
edge[u].end(); iter
++
)
28
{
29
if
(c[u][
*
iter]
>
f[u][
*
iter]
&&
h[
*
iter]
<
h[u])
30
h[u]
=
h[
*
iter];
31
}
32
h[u]
++
;
33
}
34
35
void
Discharge(
int
u)
//
discharge the residual flow of vertex u
36
{
37
list
<
int
>
::iterator iter
=
edge[u].begin();
38
while
(e[u]
>
0
)
39
{
40
if
(iter
==
edge[u].end())
41
{
42
Relable(u);
43
iter
=
edge[u].begin();
44
}
45
if
(h[u]
==
h[
*
iter]
+
1
&&
c[u][
*
iter]
>
f[u][
*
iter])
46
{
47
Push(u,
*
iter);
48
if
(e[
*
iter]
>
0
&&
!
flag[
*
iter])
49
ev.push_back(
*
iter);
50
}
51
++
iter;
52
}
53
}
54
55
void
Init_PreFlow()
56
{
57
ev.clear();
58
h[
0
]
=
n;
59
e[
0
]
=
0
;
60
memset(flag,
0
,
sizeof
(flag));
61
memset(f,
0
,
sizeof
(f));
62
flag[
0
]
=
flag[n
-
1
]
=
true
;
63
for
(
int
u
=
1
; u
<
n; u
++
)
64
{
65
f[
0
][u]
=
c[
0
][u];
66
f[u][
0
]
=
-
f[
0
][u];
67
e[u]
=
c[
0
][u];
68
if
(e[u]
>
0
&&
!
flag[u])
69
{
70
ev.push_back(u);
71
flag[u]
=
true
;
72
}
73
}
74
75
//
construct link list
76
for
(
int
u
=
0
; u
<
n; u
++
)
77
for
(
int
v
=
u
+
1
; v
<
n; v
++
)
78
{
79
if
(c[u][v]
>
0
||
c[v][u]
>
0
)
80
{
81
edge[u].push_back(v);
82
edge[v].push_back(u);
83
}
84
}
85
}
86
87
int
Push_Relable()
88
{
89
Init_PreFlow();
90
while
(
!
ev.empty())
91
{
92
int
u
=
ev.front();
93
Discharge(u);
94
ev.pop_front();
95
flag[u]
=
false
;
96
}
97
return
e[n
-
1
];
98
}
99
100
int
main()
101
{
102
int
m, u, v, w;
103
while
(scanf(
"
%d%d
"
,
&
m,
&
n)
!=
EOF)
104
{
105
memset(c,
0
,
sizeof
(c));
106
for
(
int
i
=
0
; i
<
m; i
++
)
107
{
108
scanf(
"
%d%d%d
"
,
&
u,
&
v,
&
w);
109
c[u][v]
=
w;
110
}
111
printf(
"
Max Flow is %d
"
, Push_Relable());
112
}
113
return
0
;
114
}