tests/yosupo/dinic.bipartitematching.test.cpp

View this file on GitHub
Last update: 2021-06-13 18:08:42+02:00
Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

Code

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

#include "../../code/graphs/dinic.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int l, r, m;
  cin >> l >> r >> m;

  BM bm(l, r);

  F0R(i, m) {
      int u, v;
      cin >> u >> v;
      bm.match(u, v);
  }

  vii matching = bm.matching();
  cout << SZ(matching) << endl;
  for (auto [u, v] : matching) {
    cout << u << ' ' << v << endl;
  }
}

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

#line 1 "code/graphs/dinic.cc"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/flowedge.cc"
template <typename F>
struct edge {
  edge(int from, int to, F capacity, F flow = 0)
      : mfrom(from), mto(to), mcapacity(capacity), mflow(flow) {}
  int mfrom, mto;
  F mcapacity, mflow;
  int other(int v) { return v == mfrom ? mto : mfrom; }
  F capacity(int v) { return v == mfrom ? mcapacity : 0; }
  F flow(int v) { return v == mfrom ? mflow : -mflow; }
  void adjust(int v, F amount) {
    mflow += v == mfrom ? amount : -amount;
  }
};
template <typename F>
ostream& operator<<(ostream& o, const edge<F>& e) {
  return o << e.mfrom << "-- " << e.mflow << '/'
           << e.mcapacity << " -->" << e.mto;
}
#line 3 "code/graphs/dinic.cc"
template <typename F = ll>
struct DC {
  vector<edge<F>> edges;
  vvi adj;
  vi dist, ptr;
  int S, T, N;
  DC(int n, int m = 0, int s = -1, int t = -1) {
    reset(n, m, s, t);
  }
  void buildMatchingEdges(int m) {
    F0R (i, N) add(S, i, 1);
    F0R (i, m) add(N + i, T, 1);
  }
  int add(int from, int to, F c = numeric_limits<F>::max(), F f = 0) {
    edges.eb(from, to, c, f);
    adj[from].pb(SZ(edges) - 1);
    adj[to].pb(SZ(edges) - 1);
    return SZ(edges) - 1;
  }
  int match(int from, int to) { return add(from, N + to, 1);}
  vii matching() {
    vii res; res.reserve(maxflow());
    for (const auto& e : edges)
      if (e.mflow == 1 and e.mfrom != S and e.mto != T)
        res.eb(e.mfrom, e.mto - N);
    return res;
  }
  void clear() { edges.clear(); adj.clear(); }
  void reset(int n, int m = 0, int s = -1, int t = -1) {
    clear();
    adj.resize((N = n) + m + (s == -1) + (t == -1));
    S = s == -1 ? n + m : s;
    T = t == -1 ? n + m + (s == -1) : t;
    if (m != 0) buildMatchingEdges(m);
  }
  bool bfs(int s, int t) {
    dist.assign(SZ(adj), SZ(adj));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (SZ(q)) {
      int v = q.front(); q.pop();
      for (int i : adj[v]) {
        auto& e = edges[i];
        if (dist[e.other(v)] == SZ(adj) && e.flow(v) < e.capacity(v)) {
          dist[e.other(v)] = dist[v] + 1;
          q.push(e.other(v));
        }
      }
    }
    return dist[t] < SZ(adj);
  }
  F dfs(int v, int t, F available) {
    if (v == t || !available) return available;
    F pushed = 0;
    for (; ptr[v] < SZ(adj[v]); ++ptr[v]) {
      auto& e = edges[adj[v][ptr[v]]];
      if (dist[v] + 1 != dist[e.other(v)])
        continue;
      F wasPushed = dfs(e.other(v), t,
                        min(available - pushed, e.capacity(v) - e.flow(v)));
      pushed += wasPushed;
      e.adjust(v, wasPushed);
      if (pushed == available) return pushed;
    }
    return pushed;
  }
  F maxflow() {
    return maxflow(S, T);
  }
  F maxflow(int s, int t) {
    F f = 0;
    for (;;) {
      if (!bfs(s, t)) return f;
      ptr.assign(SZ(adj), 0);
      f += dfs(s, t, numeric_limits<F>::max());
    }
  }
};
using BM = DC<int>;
#line 4 "tests/yosupo/dinic.bipartitematching.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int l, r, m;
  cin >> l >> r >> m;

  BM bm(l, r);

  F0R(i, m) {
      int u, v;
      cin >> u >> v;
      bm.match(u, v);
  }

  vii matching = bm.matching();
  cout << SZ(matching) << endl;
  for (auto [u, v] : matching) {
    cout << u << ' ' << v << endl;
  }
}