test/yosupo/graph/bipartitematching_dinitz.test.cpp

• View this file on GitHub
• Last update: 2025-09-20 17:47:50+07:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• Dinitz's Algorithm (graph/dinitz.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#include <bits/stdc++.h>
using namespace std;

#include "graph/dinitz.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int l, r, m;
    cin >> l >> r >> m;

    Dinitz<int> g(l + r + 2);
    while (m--) {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, v + l, 1);
    }

    for (int i = 0; i < l; i++) g.add_edge(l + r, i, 1);
    for (int i = l; i < l + r; i++) g.add_edge(i, l + r + 1, 1);

    cout << g.max_flow(l + r, l + r + 1) << "\n";
    for (int i = 0; i < l; i++)
        for (auto &e : g.g[i])
            if (e.cap == 0 && e.to < l + r)
                cout << i << " " << e.to - l << "\n";
}

#line 1 "test/yosupo/graph/bipartitematching_dinitz.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#include <bits/stdc++.h>
using namespace std;

#line 2 "graph/dinitz.hpp"

// clang-format off
template<class T, int K = 31> struct Dinitz {
    Dinitz() {}
    Dinitz(int n) : g(n), lvl(n), iter(n) {}

    void add_edge(int u, int v, T cap, T rcap = 0) {
        g[u].push_back({v, (int)g[v].size(), cap});
        g[v].push_back({u, (int)g[u].size() - 1, rcap});
    }
    auto &operator[](int i) { return g[i]; }

    T max_flow(int s, int t) {
        T flow = 0;
        for (int k = K; k--;) {
            while (build_dag(s, t, k)) {
                fill(begin(iter), end(iter), 0);
                while (T f = push_flow(s, t, FLOW_INF)) flow += f;
            }
        }
        return flow;
    }
    set<int> min_cut(int s) {
        stack<int> st;
        set<int> vis;
        st.push(s);
        vis.insert(s);
        while (st.size()) {
            int v = st.top();
            st.pop();
            for (auto &[to, rev, cap] : g[v]) 
                if (cap && !vis.count(to)) 
                    vis.insert(to), st.push(to);
        }
        return vis;
    }

    static constexpr T FLOW_INF = numeric_limits<T>::max() / 2;
    struct Edge {
        int to, rev;
        T cap;
    };

    vector<vector<Edge>> g;
    vector<int> lvl, iter;

    bool build_dag(int s, int t, int k) {
        fill(begin(lvl), end(lvl), -1);
        lvl[s] = 0;
        queue<int> q; q.push(s);
        while (q.size()) {
            int v = q.front(); q.pop();
            for (auto &[to, _rev, cap] : g[v]) {
                if (lvl[to] == -1 && cap >> k) {
                    lvl[to] = lvl[v] + 1;
                    q.push(to);
                }
            }
        }
        return lvl[t] != -1;
    }
    T push_flow(int v, int t, T flow) {
        if (v == t) return flow;
        for (int &i = iter[v]; i < g[v].size(); i++) {
            auto &[to, rev, cap] = g[v][i];
            if (lvl[v] < lvl[to] && cap > 0) {
                if (T delta = push_flow(to, t, min(flow, cap))) {
                    cap -= delta, g[to][rev].cap += delta;
                    return delta;
                }
            }
        }
        return 0;
    }
};
// clang-format on
#line 7 "test/yosupo/graph/bipartitematching_dinitz.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int l, r, m;
    cin >> l >> r >> m;

    Dinitz<int> g(l + r + 2);
    while (m--) {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, v + l, 1);
    }

    for (int i = 0; i < l; i++) g.add_edge(l + r, i, 1);
    for (int i = l; i < l + r; i++) g.add_edge(i, l + r + 1, 1);

    cout << g.max_flow(l + r, l + r + 1) << "\n";
    for (int i = 0; i < l; i++)
        for (auto &e : g.g[i])
            if (e.cap == 0 && e.to < l + r)
                cout << i << " " << e.to - l << "\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	augmented_cycle_00	AC	2355 ms	24 MB
g++	augmented_cycle_01	AC	1393 ms	25 MB
g++	augmented_cycle_02	AC	2384 ms	25 MB
g++	cycle_00	AC	1976 ms	28 MB
g++	cycle_01	AC	1999 ms	27 MB
g++	example_00	AC	4 ms	4 MB
g++	issue1068_00	AC	4 ms	4 MB
g++	issue1068_large_00	AC	62 ms	23 MB
g++	issue1068_large_01	AC	58 ms	21 MB
g++	issue1068_large_02	AC	84 ms	23 MB
g++	issue1068_large_03	AC	59 ms	21 MB
g++	issue1068_large_04	AC	59 ms	21 MB
g++	issue1068_large_05	AC	72 ms	21 MB
g++	issue1124_00	AC	157 ms	16 MB
g++	issue1124_01	AC	50 ms	16 MB
g++	issue1124_02	AC	45 ms	16 MB
g++	kuhn_killer_00	AC	70 ms	25 MB
g++	line_00	AC	81 ms	26 MB
g++	line_01	AC	82 ms	26 MB
g++	line_random_00	AC	2007 ms	28 MB
g++	line_random_01	AC	2038 ms	31 MB
g++	many_paths_00	AC	1041 ms	26 MB
g++	many_paths_01	AC	817 ms	26 MB
g++	many_paths_02	AC	992 ms	26 MB
g++	many_smalls_00	AC	106 ms	19 MB
g++	many_smalls_01	AC	102 ms	19 MB
g++	max_random_00	AC	249 ms	24 MB
g++	max_random_01	AC	274 ms	24 MB
g++	max_random_02	AC	249 ms	24 MB
g++	random_00	AC	18 ms	11 MB
g++	random_01	AC	58 ms	15 MB
g++	random_02	AC	88 ms	15 MB
g++	random_03	AC	73 ms	13 MB
g++	random_04	AC	22 ms	12 MB
g++	random_05	AC	30 ms	10 MB
g++	random_06	AC	246 ms	18 MB
g++	random_07	AC	33 ms	12 MB
g++	random_08	AC	44 ms	14 MB
g++	random_09	AC	68 ms	15 MB
g++	unique_matching_00	AC	2180 ms	27 MB
g++	unique_matching_01	AC	1908 ms	26 MB
g++	unique_matching_02	AC	1470 ms	25 MB
g++	unique_matching_03	AC	783 ms	25 MB
g++	unique_matching_04	AC	508 ms	25 MB
clang++	augmented_cycle_00	AC	2353 ms	25 MB
clang++	augmented_cycle_01	AC	1274 ms	25 MB
clang++	augmented_cycle_02	AC	2479 ms	25 MB
clang++	cycle_00	AC	2069 ms	29 MB
clang++	cycle_01	AC	2062 ms	28 MB
clang++	example_00	AC	4 ms	4 MB
clang++	issue1068_00	AC	4 ms	4 MB
clang++	issue1068_large_00	AC	63 ms	25 MB
clang++	issue1068_large_01	AC	57 ms	21 MB
clang++	issue1068_large_02	AC	85 ms	25 MB
clang++	issue1068_large_03	AC	57 ms	21 MB
clang++	issue1068_large_04	AC	58 ms	21 MB
clang++	issue1068_large_05	AC	73 ms	21 MB
clang++	issue1124_00	AC	159 ms	16 MB
clang++	issue1124_01	AC	49 ms	16 MB
clang++	issue1124_02	AC	44 ms	16 MB
clang++	kuhn_killer_00	AC	70 ms	25 MB
clang++	line_00	AC	81 ms	26 MB
clang++	line_01	AC	84 ms	26 MB
clang++	line_random_00	AC	2026 ms	28 MB
clang++	line_random_01	AC	2068 ms	34 MB
clang++	many_paths_00	AC	1099 ms	26 MB
clang++	many_paths_01	AC	788 ms	26 MB
clang++	many_paths_02	AC	1003 ms	26 MB
clang++	many_smalls_00	AC	111 ms	19 MB
clang++	many_smalls_01	AC	101 ms	19 MB
clang++	max_random_00	AC	253 ms	24 MB
clang++	max_random_01	AC	270 ms	24 MB
clang++	max_random_02	AC	258 ms	24 MB
clang++	random_00	AC	17 ms	11 MB
clang++	random_01	AC	58 ms	15 MB
clang++	random_02	AC	88 ms	15 MB
clang++	random_03	AC	73 ms	13 MB
clang++	random_04	AC	22 ms	12 MB
clang++	random_05	AC	30 ms	10 MB
clang++	random_06	AC	249 ms	18 MB
clang++	random_07	AC	34 ms	12 MB
clang++	random_08	AC	44 ms	14 MB
clang++	random_09	AC	67 ms	15 MB
clang++	unique_matching_00	AC	2307 ms	29 MB
clang++	unique_matching_01	AC	1973 ms	26 MB
clang++	unique_matching_02	AC	1517 ms	26 MB
clang++	unique_matching_03	AC	812 ms	25 MB
clang++	unique_matching_04	AC	530 ms	25 MB

Back to top page