This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=ja
#include "../MaxFlow.cpp"
int main() {
int v, e;
cin >> v >> e;
Dinic<int> g(v);
for (int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
g.add_edge(a, b, c);
}
cout << g.max_flow(0, v - 1) << endl;
}
#line 1 "test/MaxFlow.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=ja
#line 1 "MaxFlow.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class Cap>
struct Dinic {
struct edge {
int to, rev;
Cap cap;
};
int N;
vector<vector<edge>> g;
vector<int> level, iter;
Dinic() = default;
Dinic(int n) : N(n), level(n), iter(n), g(n) {}
void add_edge(int from, int to, Cap cap) {
g[from].push_back(edge{to, (int)g[to].size(), cap});
g[to].push_back(edge{from, (int)g[from].size() - 1, (Cap)0});
}
void bfs(int s) {
fill(level.begin(), level.end(), -1);
queue<int> que;
level[s] = 0;
que.push(0);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < g[v].size(); i++) {
edge &e = g[v][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
Cap dfs(int v, int t, Cap f) {
if (v == t) return f;
for (int &i = iter[v]; i < (int)g[v].size(); i++) {
edge &e = g[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
Cap d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
Cap max_flow(int s, int t) { return max_flow(s, t, numeric_limits<Cap>::max()); }
Cap max_flow(int s, int t, Cap flow_limit) {
Cap flow = 0;
while (flow < flow_limit) {
bfs(s);
if (level[t] == -1) break;
fill(iter.begin(), iter.end(), 0);
Cap f;
while (flow < flow_limit) {
Cap f = dfs(s, t, flow_limit - flow);
if (!f) break;
flow += f;
}
}
return flow;
}
};
#line 3 "test/MaxFlow.test.cpp"
int main() {
int v, e;
cin >> v >> e;
Dinic<int> g(v);
for (int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
g.add_edge(a, b, c);
}
cout << g.max_flow(0, v - 1) << endl;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_sample_00.in |
![]() |
5 ms | 3 MB |
g++ | 01_small_00.in |
![]() |
5 ms | 4 MB |
g++ | 01_small_01.in |
![]() |
4 ms | 4 MB |
g++ | 01_small_02.in |
![]() |
4 ms | 4 MB |
g++ | 01_small_03.in |
![]() |
4 ms | 4 MB |
g++ | 02_corner_00.in |
![]() |
4 ms | 3 MB |
g++ | 02_corner_01.in |
![]() |
4 ms | 3 MB |
g++ | 02_corner_02.in |
![]() |
4 ms | 4 MB |
g++ | 02_corner_03.in |
![]() |
4 ms | 3 MB |
g++ | 03_random_00.in |
![]() |
4 ms | 3 MB |
g++ | 03_random_01.in |
![]() |
4 ms | 4 MB |
g++ | 03_random_02.in |
![]() |
4 ms | 4 MB |
g++ | 03_random_03.in |
![]() |
4 ms | 4 MB |
g++ | 03_random_04.in |
![]() |
4 ms | 4 MB |
g++ | 03_random_05.in |
![]() |
4 ms | 3 MB |
g++ | 03_random_06.in |
![]() |
4 ms | 4 MB |
g++ | 03_random_07.in |
![]() |
5 ms | 4 MB |
g++ | 04_rand_00.in |
![]() |
4 ms | 3 MB |
g++ | 04_rand_01.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_02.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_03.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_04.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_05.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_06.in |
![]() |
4 ms | 4 MB |
g++ | 04_rand_07.in |
![]() |
4 ms | 4 MB |
g++ | 05_large_00.in |
![]() |
5 ms | 4 MB |
g++ | 05_large_01.in |
![]() |
5 ms | 4 MB |
g++ | 05_large_02.in |
![]() |
4 ms | 4 MB |
g++ | 05_large_03.in |
![]() |
4 ms | 3 MB |
g++ | 05_large_04.in |
![]() |
4 ms | 4 MB |
g++ | 05_large_05.in |
![]() |
4 ms | 4 MB |
g++ | 06_biased_00.in |
![]() |
4 ms | 3 MB |
g++ | 06_biased_01.in |
![]() |
4 ms | 3 MB |
g++ | 06_biased_02.in |
![]() |
4 ms | 4 MB |
g++ | 06_biased_03.in |
![]() |
4 ms | 4 MB |
g++ | 06_biased_04.in |
![]() |
5 ms | 4 MB |
g++ | 06_biased_05.in |
![]() |
4 ms | 3 MB |
g++ | 06_biased_06.in |
![]() |
5 ms | 4 MB |
g++ | 06_biased_07.in |
![]() |
4 ms | 3 MB |
g++ | 06_biased_08.in |
![]() |
4 ms | 3 MB |
clang++ | 00_sample_00.in |
![]() |
5 ms | 4 MB |
clang++ | 01_small_00.in |
![]() |
5 ms | 3 MB |
clang++ | 01_small_01.in |
![]() |
5 ms | 4 MB |
clang++ | 01_small_02.in |
![]() |
4 ms | 4 MB |
clang++ | 01_small_03.in |
![]() |
4 ms | 4 MB |
clang++ | 02_corner_00.in |
![]() |
4 ms | 3 MB |
clang++ | 02_corner_01.in |
![]() |
4 ms | 4 MB |
clang++ | 02_corner_02.in |
![]() |
4 ms | 3 MB |
clang++ | 02_corner_03.in |
![]() |
4 ms | 4 MB |
clang++ | 03_random_00.in |
![]() |
4 ms | 3 MB |
clang++ | 03_random_01.in |
![]() |
4 ms | 4 MB |
clang++ | 03_random_02.in |
![]() |
4 ms | 4 MB |
clang++ | 03_random_03.in |
![]() |
4 ms | 4 MB |
clang++ | 03_random_04.in |
![]() |
4 ms | 3 MB |
clang++ | 03_random_05.in |
![]() |
4 ms | 3 MB |
clang++ | 03_random_06.in |
![]() |
4 ms | 4 MB |
clang++ | 03_random_07.in |
![]() |
4 ms | 4 MB |
clang++ | 04_rand_00.in |
![]() |
4 ms | 3 MB |
clang++ | 04_rand_01.in |
![]() |
4 ms | 3 MB |
clang++ | 04_rand_02.in |
![]() |
4 ms | 3 MB |
clang++ | 04_rand_03.in |
![]() |
4 ms | 4 MB |
clang++ | 04_rand_04.in |
![]() |
4 ms | 3 MB |
clang++ | 04_rand_05.in |
![]() |
4 ms | 4 MB |
clang++ | 04_rand_06.in |
![]() |
4 ms | 3 MB |
clang++ | 04_rand_07.in |
![]() |
4 ms | 3 MB |
clang++ | 05_large_00.in |
![]() |
5 ms | 4 MB |
clang++ | 05_large_01.in |
![]() |
5 ms | 4 MB |
clang++ | 05_large_02.in |
![]() |
4 ms | 4 MB |
clang++ | 05_large_03.in |
![]() |
4 ms | 4 MB |
clang++ | 05_large_04.in |
![]() |
4 ms | 4 MB |
clang++ | 05_large_05.in |
![]() |
4 ms | 4 MB |
clang++ | 06_biased_00.in |
![]() |
4 ms | 4 MB |
clang++ | 06_biased_01.in |
![]() |
4 ms | 3 MB |
clang++ | 06_biased_02.in |
![]() |
4 ms | 3 MB |
clang++ | 06_biased_03.in |
![]() |
4 ms | 3 MB |
clang++ | 06_biased_04.in |
![]() |
4 ms | 3 MB |
clang++ | 06_biased_05.in |
![]() |
4 ms | 4 MB |
clang++ | 06_biased_06.in |
![]() |
5 ms | 4 MB |
clang++ | 06_biased_07.in |
![]() |
4 ms | 3 MB |
clang++ | 06_biased_08.in |
![]() |
4 ms | 4 MB |