test/MaxFlow.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=ja

Depends on

• MaxFlow.cpp

Code

// 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;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	5 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	02_corner_00.in	AC	4 ms	3 MB
g++	02_corner_01.in	AC	4 ms	3 MB
g++	02_corner_02.in	AC	4 ms	4 MB
g++	02_corner_03.in	AC	4 ms	3 MB
g++	03_random_00.in	AC	4 ms	3 MB
g++	03_random_01.in	AC	4 ms	4 MB
g++	03_random_02.in	AC	4 ms	4 MB
g++	03_random_03.in	AC	4 ms	4 MB
g++	03_random_04.in	AC	4 ms	4 MB
g++	03_random_05.in	AC	4 ms	3 MB
g++	03_random_06.in	AC	4 ms	4 MB
g++	03_random_07.in	AC	5 ms	4 MB
g++	04_rand_00.in	AC	4 ms	3 MB
g++	04_rand_01.in	AC	4 ms	4 MB
g++	04_rand_02.in	AC	4 ms	4 MB
g++	04_rand_03.in	AC	4 ms	4 MB
g++	04_rand_04.in	AC	4 ms	4 MB
g++	04_rand_05.in	AC	4 ms	4 MB
g++	04_rand_06.in	AC	4 ms	4 MB
g++	04_rand_07.in	AC	4 ms	4 MB
g++	05_large_00.in	AC	5 ms	4 MB
g++	05_large_01.in	AC	5 ms	4 MB
g++	05_large_02.in	AC	4 ms	4 MB
g++	05_large_03.in	AC	4 ms	3 MB
g++	05_large_04.in	AC	4 ms	4 MB
g++	05_large_05.in	AC	4 ms	4 MB
g++	06_biased_00.in	AC	4 ms	3 MB
g++	06_biased_01.in	AC	4 ms	3 MB
g++	06_biased_02.in	AC	4 ms	4 MB
g++	06_biased_03.in	AC	4 ms	4 MB
g++	06_biased_04.in	AC	5 ms	4 MB
g++	06_biased_05.in	AC	4 ms	3 MB
g++	06_biased_06.in	AC	5 ms	4 MB
g++	06_biased_07.in	AC	4 ms	3 MB
g++	06_biased_08.in	AC	4 ms	3 MB
clang++	00_sample_00.in	AC	5 ms	4 MB
clang++	01_small_00.in	AC	5 ms	3 MB
clang++	01_small_01.in	AC	5 ms	4 MB
clang++	01_small_02.in	AC	4 ms	4 MB
clang++	01_small_03.in	AC	4 ms	4 MB
clang++	02_corner_00.in	AC	4 ms	3 MB
clang++	02_corner_01.in	AC	4 ms	4 MB
clang++	02_corner_02.in	AC	4 ms	3 MB
clang++	02_corner_03.in	AC	4 ms	4 MB
clang++	03_random_00.in	AC	4 ms	3 MB
clang++	03_random_01.in	AC	4 ms	4 MB
clang++	03_random_02.in	AC	4 ms	4 MB
clang++	03_random_03.in	AC	4 ms	4 MB
clang++	03_random_04.in	AC	4 ms	3 MB
clang++	03_random_05.in	AC	4 ms	3 MB
clang++	03_random_06.in	AC	4 ms	4 MB
clang++	03_random_07.in	AC	4 ms	4 MB
clang++	04_rand_00.in	AC	4 ms	3 MB
clang++	04_rand_01.in	AC	4 ms	3 MB
clang++	04_rand_02.in	AC	4 ms	3 MB
clang++	04_rand_03.in	AC	4 ms	4 MB
clang++	04_rand_04.in	AC	4 ms	3 MB
clang++	04_rand_05.in	AC	4 ms	4 MB
clang++	04_rand_06.in	AC	4 ms	3 MB
clang++	04_rand_07.in	AC	4 ms	3 MB
clang++	05_large_00.in	AC	5 ms	4 MB
clang++	05_large_01.in	AC	5 ms	4 MB
clang++	05_large_02.in	AC	4 ms	4 MB
clang++	05_large_03.in	AC	4 ms	4 MB
clang++	05_large_04.in	AC	4 ms	4 MB
clang++	05_large_05.in	AC	4 ms	4 MB
clang++	06_biased_00.in	AC	4 ms	4 MB
clang++	06_biased_01.in	AC	4 ms	3 MB
clang++	06_biased_02.in	AC	4 ms	3 MB
clang++	06_biased_03.in	AC	4 ms	3 MB
clang++	06_biased_04.in	AC	4 ms	3 MB
clang++	06_biased_05.in	AC	4 ms	4 MB
clang++	06_biased_06.in	AC	5 ms	4 MB
clang++	06_biased_07.in	AC	4 ms	3 MB
clang++	06_biased_08.in	AC	4 ms	4 MB

Back to top page