[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; }
ディスカッション
コメント一覧
まだ、コメントがありません