[AOJ] GRL_7_A Bipartite Matching

問題

方針

2部マッチングの解説は、二部マッチングの解説を参照してください。二部グラフの最大マッチングを求めるアルゴリズムについては、蟻本の p. 197 のコードを利用します。

\( X \) の頂点と \( Y \) の頂点の番号が被ることがるので、隣接リストを作るときに \( Y \) の頂点に \( 100 \) を足して被らないようにします。

コード

提出したコード

最大マッチング数

static const int MAX_V = 200;
int V, E;
vector<int> G[MAX_V];
int match[MAX_V];
int used[MAX_V];

// u と v を結ぶ辺をグラフに追加する
void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}

// 増加パスを DFS で探す
bool dfs(int v) {
  used[v] = true;
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i];
    int w = match[u];
    if (w < 0 || !used[w] && dfs(w)) {
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

// 二部グラフの最大マッチングを求める
int biparticle_matching() {
  int res = 0;
  memset(match, -1, sizeof(match));
  for (int v = 0; v < V; v++) {
    if (match[v] < 0) {
      memset(used, 0, sizeof(used));
      if (dfs(v)) res++;
    }
  }
  return res;
}