二部グラフの最大マッチング

考察タイム終わった後実際に簡単な4問は解いてみた。
PKU2060で初めて最大流量を使わない2部グラフの最大マッチングのコードを書いた。Web上にメモっとこ。

typedef vector<vector<int> > graph;
struct BGM {
  int L, R; //左右のノード数
  graph g;
  vector<int> r2l; //右->左への対応
  BGM (int L, int R) : L(L), R(R), g(L), r2l(R,-1) {}
  void add_edge(int l, int r) {
    g[l].push_back(r);
  }
  bool augment(int l, vector<bool>& visited) {
    if (l == -1) return true;
    if (visited[l]) return false;
    visited[l] = true;
    vector<int>& e = g[l];
    for (int i = 0; i < e.size(); i++) {
      int r = e[i];
      if (augment(r2l[r],visited)) {
        r2l[r] = l;
        return true;
      }
    }
    return false;
  }
  int match() {
    int cnt = 0;
    for (int l = 0; l < L; l++) {
      vector<bool> visited(L);
      if (augment(l,visited)) ++cnt;
    }
    return cnt;
  }
};