tests/Bipartite_Matching_Dinic.test.cpp

View this file on GitHub
Last update: 2025-11-28 10:18:48+07:00
Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

Code

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

#include "../misc/macros.h"
#include "../graph/Dinic.h"

void solve() {
  int L, R, M;
  cin >> L >> R >> M;

  // Xây dựng đồ thị:
  // 0 -> L-1: Đỉnh trái
  // L -> L+R-1: Đỉnh phải
  // S = L+R, T = L+R+1
  int S = L + R, T = L + R + 1;
  Dinic dinic(T + 1);

  // Nối S -> Left
  for (int i = 0; i < L; ++i) dinic.addEdge(S, i, 1);
  
  // Nối Right -> T
  for (int i = 0; i < R; ++i) dinic.addEdge(L + i, T, 1);

  // Nối Left -> Right (Edges)
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    dinic.addEdge(u, L + v, 1);
  }

  // Tính luồng cực đại = Cặp ghép cực đại
  cout << dinic.calc(S, T) << "\n";

  // Truy vết in kết quả
  // Duyệt qua các đỉnh bên trái (0 -> L-1)
  for (int i = 0; i < L; ++i) {
    for (auto& e : dinic.adj[i]) {
      if (e.to >= L && e.to < L + R && e.c == 0) {
        cout << i << " " << e.to - L << "\n";
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc--) solve();
}

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

#line 1 "misc/macros.h"
// #pragma GCC optimize("Ofast,unroll-loops")       // unroll long, simple loops
// #pragma GCC target("avx2,fma")                   // vectorizing code
// #pragma GCC target("lzcnt,popcnt,abm,bmi,bmi2")  // for fast bitset operation

#include <bits/extc++.h>
#include <tr2/dynamic_bitset>

using namespace std;
using namespace __gnu_pbds;  // ordered_set, gp_hash_table
// using namespace __gnu_cxx; // rope

// for templates to work
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define pb push_back
#define eb emplace_back
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
using pii = pair<i32, i32>;
using vi = vector<i32>;

// fast map
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {  // customize hash function for gp_hash_table
  int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<int, int, chash> table;

/* ordered set
    find_by_order(k): returns an iterator to the k-th element (0-based)
    order_of_key(k): returns the number of elements in the set that are strictly less than k
*/
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*  rope
    rope <int> cur = v.substr(l, r - l + 1);
    v.erase(l, r - l + 1);
    v.insert(v.mutable_begin(), cur);
*/
#line 1 "graph/Dinic.h"
struct Dinic {
  struct Edge {
    int to, rev;
    i64 c, oc;
    i64 flow() { return max(oc - c, i64(0)); }  // if you need flows
  };
  vi lvl, ptr, q;
  vector<vector<Edge>> adj;
  Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
  void addEdge(int a, int b, i64 c, i64 rcap = 0) {
    adj[a].pb({b, sz(adj[b]), c, c});
    adj[b].pb({a, sz(adj[a]) - 1, rcap, rcap});
  }
  i64 dfs(int v, int t, i64 f) {
    if (v == t || !f) return f;
    for (int& i = ptr[v]; i < sz(adj[v]); i++) {
      Edge& e = adj[v][i];
      if (lvl[e.to] == lvl[v] + 1)
        if (i64 p = dfs(e.to, t, min(f, e.c))) {
          e.c -= p, adj[e.to][e.rev].c += p;
          return p;
        }
    }
    return 0;
  }
  i64 calc(int s, int t) {
    i64 flow = 0;
    q[0] = s;
    // 'int L=30' maybe faster for random data
    for (int L = 0; L < 31; ++L) {
      do {
        lvl = ptr = vi(sz(q));
        int qi = 0, qe = lvl[s] = 1;
        while (qi < qe && !lvl[t]) {
          int v = q[qi++];
          for (Edge e : adj[v])
            if (!lvl[e.to] && e.c >> (30 - L))
              q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
        }
        while (i64 p = dfs(s, t, LLONG_MAX)) flow += p;
      } while (lvl[t]);
    }
    return flow;
  }
  bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
#line 5 "tests/Bipartite_Matching_Dinic.test.cpp"

void solve() {
  int L, R, M;
  cin >> L >> R >> M;

  // Xây dựng đồ thị:
  // 0 -> L-1: Đỉnh trái
  // L -> L+R-1: Đỉnh phải
  // S = L+R, T = L+R+1
  int S = L + R, T = L + R + 1;
  Dinic dinic(T + 1);

  // Nối S -> Left
  for (int i = 0; i < L; ++i) dinic.addEdge(S, i, 1);
  
  // Nối Right -> T
  for (int i = 0; i < R; ++i) dinic.addEdge(L + i, T, 1);

  // Nối Left -> Right (Edges)
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    dinic.addEdge(u, L + v, 1);
  }

  // Tính luồng cực đại = Cặp ghép cực đại
  cout << dinic.calc(S, T) << "\n";

  // Truy vết in kết quả
  // Duyệt qua các đỉnh bên trái (0 -> L-1)
  for (int i = 0; i < L; ++i) {
    for (auto& e : dinic.adj[i]) {
      if (e.to >= L && e.to < L + R && e.c == 0) {
        cout << i << " " << e.to - L << "\n";
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc--) solve();
}