1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
/*
* Max flow EK with DFS.
*/
const int INF = 0x70000000;
int size[10];
int to[10][10];
int cap[10][10];
int rev[10][10];
int used[10];
void my_memset(int arr[], int val, int n)
{
int i = 0;
while (i < n) {
arr[i] = val;
i = i + 1;
}
}
void add_node(int u, int v, int c)
{
to[u][size[u]] = v;
cap[u][size[u]] = c;
rev[u][size[u]] = size[v];
to[v][size[v]] = u;
cap[v][size[v]] = 0;
rev[v][size[v]] = size[u];
size[u] = size[u] + 1;
size[v] = size[v] + 1;
}
int dfs(int s, int t, int f)
{
if (s == t)
return f;
used[s] = 1;
int i = 0;
while (i < size[s]) {
if (used[to[s][i]]) { i = i + 1; continue; }
if (cap[s][i] <= 0) { i = i + 1; continue; }
int min_f;
if (f < cap[s][i])
min_f = f;
else
min_f = cap[s][i];
int d = dfs(to[s][i], t, min_f);
if (d > 0) {
cap[s][i] = cap[s][i] - d;
cap[to[s][i]][rev[s][i]] = cap[to[s][i]][rev[s][i]] + d;
return d;
}
i = i + 1;
}
return 0;
}
int max_flow(int s, int t)
{
int flow = 0;
while (1) {
my_memset(used, 0, 10);
int f = dfs(s, t, INF);
if (f == 0)
return flow;
flow = flow + f;
}
}
int main()
{
int V, E;
V = getint();
E = getint();
my_memset(size, 0, 10);
while (E > 0) {
int u, v;
u = getint();
v = getint();
int c = getint();
add_node(u, v, c);
E = E - 1;
}
putint(max_flow(1, V));
putch(10);
return 0;
}
|
