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
|
# define INF 1023456789
bool bfs(int s, int t, vector<vector<int>>& adj, vector<bool>& visited,
vector<int>& d) {
queue<int> Q;
Q.push(s);
visited[s] = 1;
while (!Q.empty()) {
int now = Q.front();
for (int i = 0; i < adj[now].size(); i++) {
if (adj[now][i] > 0 && !visited[i]) {
d[i] = d[now] + 1;
visited[i] = 1;
if (i == t) return 1;
Q.push(i);
}
}
Q.pop();
}
return 0;
}
int dfs(int now, int maxf, int s, int t, vector<vector<int>>& adj,
vector<bool>& visited, vector<int>& d) {
if (now == t) return maxf;
if (visited[now]) return 0;
visited[now] = 1;
for (int i = 0; i < adj[now].size(); i++) {
int tmp = adj[now][i];
if (tmp > 0 && d[i] == d[now] + 1) {
int f = dfs(i, min(tmp, maxf), s, t, adj, visited, d);
if (f) {
adj[now][i] -= f;
adj[i][now] += f;
return f;
}
}
}
return 0;
}
int solve(int n, int m) {
int a, b, c, s, t, flow;
s = 1;
t = m;
vector<vector<int>> adj(m + 2, vector<int>(m + 2, 0));
vector<bool> visited(m + 2, 0);
vector<int> d(m + 2, 0);
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
adj[a][b] += c;
}
flow = 0;
while (bfs(s, t, adj, visited, d)) {
while (1) {
visited.clear();
visited.resize(m + 2, 0);
int f = dfs(s, INF, s, t, adj, visited, d);
if (!f) break;
flow += f;
}
visited.clear();
visited.resize(m + 2, 0);
d.clear();
d.resize(m + 2, 0);
}
cout << flow << "\n";
}
int main() {
int n, m;
while (cin >> n >> m) solve(n, m);
}
|