verify/bipartitematching.test.cpp

• View this file on GitHub
• Last update: 2019-12-04 00:43:23+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• lib/classes/dinic.cpp

Code

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

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

#include "../lib/classes/dinic.cpp"


signed main() {

    int l, r, m;
    cin >> l >> r >> m;
    Dinic<int> d(l + r + 2);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        d.add(a, l + b, 1);
    }
    for(int i = 0; i < l; ++i)
        d.add(l + r, i, 1);
    for(int i = 0; i < r; ++i)
        d.add(l + i, l + r + 1, 1);
    cout << d.solve(l + r, l + r + 1) << endl;
    for(int i = 0; i < l + r; ++i)
        for(auto& e : d.edges[i]){
            if(e.to >= l + r || i >= e.to)
                continue;
            if(e.cap == 0)
                cout << i << " " << e.to - l << endl;
        }
}

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

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

#line 1 "lib/classes/dinic.cpp"
template <typename T>
struct Dinic{
    struct Edge{
        int to, rev;
        T cap;
        Edge(int to, T cap, int rev) : to(to), rev(rev), cap(cap){}
    };

    vector<vector<Edge>> edges;
    T _inf;
    vector<T> min_cost;
    vector<int> cnt;

    Dinic(int n) : edges(n), _inf(numeric_limits<T>::max()){}

    void add(int from, int to, T cap){
        edges[from].emplace_back(to, cap, static_cast<int>(edges[to].size()));
        edges[to].emplace_back(from, 0, static_cast<int>(edges[from].size()) - 1);
    }

    bool bfs(int s, int t){
        min_cost.assign(edges.size(), -1);
        queue<int> que;
        min_cost[s] = 0;
        que.emplace(s);
        while(!que.empty() && min_cost[t] == -1){
            int x = que.front();
            que.pop();
            for(auto& ed : edges[x])
                if(ed.cap > 0 && min_cost[ed.to] == -1){
                    min_cost[ed.to] = min_cost[x] + 1;
                    que.emplace(ed.to);
                }
        }
        return min_cost[t] != -1;
    }

    T dfs(int idx, int t, T flow){
        if(idx == t)
            return flow;
        T ret = 0;
        while(cnt[idx] < edges[idx].size()){
            auto& ed = edges[idx][cnt[idx]];
            if(ed.cap > 0 && min_cost[idx] < min_cost[ed.to]){
                T d = dfs(ed.to, t, min(flow, ed.cap));
                ed.cap -= d;
                edges[ed.to][ed.rev].cap += d;
                ret += d;
                flow -= d;
                if(flow == 0)
                    break;
            }
            ++cnt[idx];
        }
        return ret;
    }

    T solve(int s, int t){
        T flow = 0;
        while(bfs(s, t)){
            cnt.assign(edges.size(), 0);
            T f = 0;
            while((f = dfs(s, t, _inf)) > 0)
                flow += f;
        }
        return flow;
    }

};

#line 8 "verify/bipartitematching.test.cpp"


signed main() {

    int l, r, m;
    cin >> l >> r >> m;
    Dinic<int> d(l + r + 2);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        d.add(a, l + b, 1);
    }
    for(int i = 0; i < l; ++i)
        d.add(l + r, i, 1);
    for(int i = 0; i < r; ++i)
        d.add(l + i, l + r + 1, 1);
    cout << d.solve(l + r, l + r + 1) << endl;
    for(int i = 0; i < l + r; ++i)
        for(auto& e : d.edges[i]){
            if(e.to >= l + r || i >= e.to)
                continue;
            if(e.cap == 0)
                cout << i << " " << e.to - l << endl;
        }
}

Back to top page