Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/graph/max_matching.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/graph/graph_template.hpp"
#include "../../../src/graph/max_matching.hpp"
int brute_max_matching(const int n, const vector<pair<int, int>>& es) {
    const int m = es.size();
    int res = 0;
    for(int bit = 0; bit < (1 << m); ++bit) {
        vector<int> used(n, false);
        int cnt = 0;
        bool ok = true;
        for(int i = 0; i < m; ++i) {
            if(!(bit >> i & 1)) continue;
            const auto& [u, v] = es[i];
            if(used[u] or used[v]) {
                ok = false;
                break;
            }
            used[u] = used[v] = true;
            ++cnt;
        }
        if(ok) res = max(res, cnt);
    }
    return res;
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
    mt19937 rng(12345);
    rep(n, 1, 9) {
        vector<pair<int, int>> all_edges;
        rep(i, 0, n) rep(j, i + 1, n) all_edges.emplace_back(i, j);
        rep(_, 0, 200) {
            Edges<int> input;
            vector<pair<int, int>> es;
            for(const auto& [u, v] : all_edges) {
                if((rng() & 1) == 0) continue;
                input.emplace_back(u, v, 1);
                es.emplace_back(u, v);
            }
            const auto got = max_matching(n, input);
            assert((int)got.size() == brute_max_matching(n, es));
            vector<int> used(n, false);
            for(const auto& e : got) {
                assert(0 <= e.from and e.from < n);
                assert(0 <= e.to and e.to < n);
                assert(!used[e.from]);
                assert(!used[e.to]);
                used[e.from] = used[e.to] = true;
            }
        }
    }
}
#line 1 "verify/unit_test/graph/max_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/graph/graph_template.hpp"
template <typename T>
struct Edge {
    int from, to;
    T cost;
    int idx;
    Edge()
        : from(-1), to(-1), cost(-1), idx(-1) {}
    Edge(const int from, const int to, const T& cost = 1, const int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
    operator int() const {
        return to;
    }
};
template <typename T>
struct Graph {
    Graph(const int N)
        : n(N), es(0), g(N) {}
    int size() const {
        return n;
    }
    int edge_size() const {
        return es;
    }
    void add_edge(const int from, const int to, const T& cost = 1) {
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }
    void add_directed_edge(const int from, const int to, const T& cost = 1) {
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        g[from].emplace_back(from, to, cost, es++);
    }
    inline vector<Edge<T>>& operator[](const int& k) {
        assert(0 <= k and k < n);
        return g[k];
    }
    inline const vector<Edge<T>>& operator[](const int& k) const {
        assert(0 <= k and k < n);
        return g[k];
    }

   private:
    int n, es;
    vector<vector<Edge<T>>> g;
};
template <typename T>
using Edges = vector<Edge<T>>;
#line 4 "src/graph/max_matching.hpp"
template <typename T>
Edges<T> max_matching(const int n, const Edges<T>& es) {
    struct GabowEdmonds {
        struct AdjEdge {
            int to, id;
        };
        int n, offset;
        vector<vector<AdjEdge>> g;
        vector<pair<int, int>> edges;
        vector<int> mate, label, first, que;
        GabowEdmonds(const int n)
            : n(n), offset(n + 1), g(n + 1), mate(n + 1), label(n + 1, -1), first(n + 1) {
            que.reserve(n + 1);
        }
        void add_edge(int u, int v) {
            ++u;
            ++v;
            const int id = offset + (int)edges.size();
            g[u].push_back({v, id});
            g[v].push_back({u, id});
            edges.emplace_back(u, v);
        }
        int find(const int v) {
            if(label[first[v]] < 0) return first[v];
            return first[v] = find(first[v]);
        }
        void rematch(const int v, const int w) {
            const int t = mate[v];
            mate[v] = w;
            if(mate[t] != v) return;
            if(label[v] < offset) {
                mate[t] = label[v];
                rematch(label[v], t);
            } else {
                const auto& [x, y] = edges[label[v] - offset];
                rematch(x, y);
                rematch(y, x);
            }
        }
        void assign_label(const int x, const int y, const int id) {
            int r = find(x), s = find(y);
            if(r == s) return;
            int join = 0;
            label[r] = label[s] = -id;
            while(true) {
                if(s != 0) swap(r, s);
                r = find(label[mate[r]]);
                if(label[r] == -id) {
                    join = r;
                    break;
                }
                label[r] = -id;
            }
            int v = first[x];
            while(v != join) {
                que.push_back(v);
                label[v] = id;
                first[v] = join;
                v = first[label[mate[v]]];
            }
            v = first[y];
            while(v != join) {
                que.push_back(v);
                label[v] = id;
                first[v] = join;
                v = first[label[mate[v]]];
            }
        }
        bool augment(const int root) {
            int head = 0;
            que.clear();
            first[root] = 0;
            label[root] = 0;
            que.push_back(root);
            while(head < (int)que.size()) {
                const int v = que[head++];
                for(const AdjEdge& e : g[v]) {
                    const int u = e.to;
                    if(mate[u] == 0 and u != root) {
                        mate[u] = v;
                        rematch(v, u);
                        return true;
                    }
                    if(label[u] >= 0) {
                        assign_label(v, u, e.id);
                    } else if(label[mate[u]] < 0) {
                        label[mate[u]] = v;
                        first[mate[u]] = u;
                        que.push_back(mate[u]);
                    }
                }
            }
            return false;
        }
        vector<pair<int, int>> solve() {
            for(int i = 1; i <= n; ++i) {
                if(mate[i] != 0) continue;
                if(augment(i)) fill(label.begin(), label.end(), -1);
            }
            vector<pair<int, int>> res;
            res.reserve(n / 2);
            for(int i = 1; i <= n; ++i) {
                if(i < mate[i]) res.emplace_back(i - 1, mate[i] - 1);
            }
            return res;
        }
    };
    GabowEdmonds matching(n);
    vector<int> deg(n);
    for(const Edge<T>& e : es) {
        assert(e.cost == 1);
        assert(0 <= e.from and e.from < n);
        assert(0 <= e.to and e.to < n);
        if(e.from == e.to) continue;
        ++deg[e.from];
        ++deg[e.to];
    }
    for(int i = 0; i < n; ++i) {
        matching.g[i + 1].reserve(deg[i]);
    }
    for(const Edge<T>& e : es) {
        if(e.from != e.to) matching.add_edge(e.from, e.to);
    }
    const vector<pair<int, int>> pairs = matching.solve();
    Edges<T> res;
    res.reserve(pairs.size());
    for(const auto& [u, v] : pairs) {
        res.emplace_back(u, v, T(1));
    }
    return res;
}
#line 5 "verify/unit_test/graph/max_matching.test.cpp"
int brute_max_matching(const int n, const vector<pair<int, int>>& es) {
    const int m = es.size();
    int res = 0;
    for(int bit = 0; bit < (1 << m); ++bit) {
        vector<int> used(n, false);
        int cnt = 0;
        bool ok = true;
        for(int i = 0; i < m; ++i) {
            if(!(bit >> i & 1)) continue;
            const auto& [u, v] = es[i];
            if(used[u] or used[v]) {
                ok = false;
                break;
            }
            used[u] = used[v] = true;
            ++cnt;
        }
        if(ok) res = max(res, cnt);
    }
    return res;
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
    mt19937 rng(12345);
    rep(n, 1, 9) {
        vector<pair<int, int>> all_edges;
        rep(i, 0, n) rep(j, i + 1, n) all_edges.emplace_back(i, j);
        rep(_, 0, 200) {
            Edges<int> input;
            vector<pair<int, int>> es;
            for(const auto& [u, v] : all_edges) {
                if((rng() & 1) == 0) continue;
                input.emplace_back(u, v, 1);
                es.emplace_back(u, v);
            }
            const auto got = max_matching(n, input);
            assert((int)got.size() == brute_max_matching(n, es));
            vector<int> used(n, false);
            for(const auto& e : got) {
                assert(0 <= e.from and e.from < n);
                assert(0 <= e.to and e.to < n);
                assert(!used[e.from]);
                assert(!used[e.to]);
                used[e.from] = used[e.to] = true;
            }
        }
    }
}
Back to top page