test/aoj/grl/grl_7_a.test.cpp

View this file on GitHub
Last update: 2024-05-06 22:18:56+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A

Depends on

lib/graph/bipartite_matching.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/bipartite_matching.hpp"

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

    int x, y, e; cin >> x >> y >> e;
    BipartiteMatching<int> bm(x + y);
    for(int i = 0; i < e; i++){
        int u, v; cin >> u >> v;
        bm.add_edge(u, v + x);
    }
    cout << bm.bipartite_matching() << "\n";
}

#line 1 "test/aoj/grl/grl_7_a.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/bipartite_matching.hpp"

template <typename T>
struct BipartiteMatching{
    vector<vector<T>> G;
    vector<T> alive, match, used;
    int timestamp;

    BipartiteMatching(int n){
        G.resize(n);
        alive.assign(n, 1);
        match.assign(n, -1);
        used.assign(n, 0);
        timestamp = 0;
    }

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

    bool dfs(int v){
        used[v] = timestamp;
        for(auto &x : G[v]){
            int y = match[x];
            if(alive[x] == 0) continue;
            if(y == -1 || (used[y] != timestamp && dfs(y))){
                match[v] = x;
                match[x] = v;
                return true;
            }
        }
        return false;
    }

    int bipartite_matching(){
        int res = 0;
        for(int i = 0; i < (int) G.size(); i++){
            if(alive[i] == 0) continue;
            if(match[i] == -1){
                ++timestamp;
                res += dfs(i);
            }
        }
        return res;
    }
};
#line 6 "test/aoj/grl/grl_7_a.test.cpp"

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

    int x, y, e; cin >> x >> y >> e;
    BipartiteMatching<int> bm(x + y);
    for(int i = 0; i < e; i++){
        int u, v; cin >> u >> v;
        bm.add_edge(u, v + x);
    }
    cout << bm.bipartite_matching() << "\n";
}