二部グラフの最大マッチング
考察タイム終わった後実際に簡単な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; } };