graph/test/bipartite_matching(slow).test.cpp

• View this file on GitHub
• Last update: 2020-11-21 18:08:42+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A

Depends on

• graph/bipartite_matching(slow).hpp

Code

#include "../bipartite_matching(slow).hpp"
#include <iostream>
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int X, Y, E;
    std::cin >> X >> Y >> E;
    BipartiteMatching graph(X + Y);
    while (E--) {
        int s, t;
        std::cin >> s >> t;
        graph.add_edge(s, X + t);
    }
    std::cout << graph.solve() << '\n';
}

#line 2 "graph/bipartite_matching(slow).hpp"
#include <iostream>
#include <vector>

// CUT begin
// Bipartite matching of undirected bipartite graph
// <https://ei1333.github.io/luzhiled/snippets/graph/bipartite-matching.html>
// Comprexity: O(VE)
struct BipartiteMatching {
    int V;                               // # of vertices
    std::vector<std::vector<int>> edges; // Adjacency list
    std::vector<int> match;              // match[i] = (Partner of i'th node) or -1 (No parter)
    std::vector<int> used;
    int timestamp;
    BipartiteMatching(int V = 0) : V(V), edges(V), match(V, -1), used(V, 0), timestamp(0) {}

    void add_edge(int u, int v) {
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    bool dfs(int v) {
        used[v] = timestamp;
        for (auto to : edges[v]) {
            if (match[to] < 0 or (used[match[to]] != timestamp and dfs(match[to]))) {
                match[v] = to;
                match[to] = v;
                return true;
            }
        }
        return false;
    }

    int solve() // Count up newly formed pairs
    {
        int ret = 0;
        for (int v = 0; v < V; v++)
            if (match[v] < 0) {
                ++timestamp;
                ret += dfs(v);
            }
        return ret;
    }

    friend std::ostream &operator<<(std::ostream &os, const BipartiteMatching &bm) {
        os << "{V=" << bm.V << ":";
        for (int i = 0; i < bm.V; i++)
            if (i < bm.match[i]) { os << "(" << i << "-" << bm.match[i] << "),"; }
        os << "}";
        return os;
    }
};
#line 3 "graph/test/bipartite_matching(slow).test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int X, Y, E;
    std::cin >> X >> Y >> E;
    BipartiteMatching graph(X + Y);
    while (E--) {
        int s, t;
        std::cin >> s >> t;
        graph.add_edge(s, X + t);
    }
    std::cout << graph.solve() << '\n';
}

Back to top page