典型的な二部マッチングの問題です。
問題概要
枚の赤いカードと、
枚の青いカードとの間でマッチングを作っていきます。
各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。
最大マッチングのサイズを求めてください。
考えたこと
二部グラフを作って、二部マッチングアルゴリズムで解くことができます。ここでは
- スーパー頂点
を追加して、最大流アルゴリズム Ford-Fulkerson 法のよる実装
- 二部マッチング専用の高速アルゴリズム Hopcroft-Karp 法による実装
を示します。
コード (Ford-Fulkerson 法による解)
#include <bits/stdc++.h> using namespace std; // グラフを表す構造体 struct Graph { // 辺を表す構造体 // rev: 逆辺 (to, from) が G[to] の中で何番目の要素か // cap: 辺 (from, to) の容量 (この値は変化する) // icap: 辺 (from, to) のもともとの容量 struct Edge { int rev, from, to, cap, icap; Edge(int r, int f, int t, int c) : rev(r), from(f), to(t), cap(c), icap(c) {} }; // 隣接リスト vector<vector<Edge>> list; // N: 頂点数 Graph(int N = 0) : list(N) { } // グラフの頂点数取得 size_t size() { return list.size(); } // Graph インスタンスを G として， // G.list[v] を G[v] と書けるようにしておく vector<Edge> &operator [] (int i) { return list[i]; } // 辺 e = (u, v) の逆辺 (v, u) を取得する Edge& redge(const Edge &e) { return list[e.to][e.rev]; } // 辺 e = (u, v) に流量 f のフローを流す // e = (u, v) の流量が f だけ減少する // このとき逆辺 (v, u) の流量を増やす void run_flow(Edge &e, int f) { e.cap -= f; redge(e).cap += f; } // 頂点 from から頂点 to へ容量 cap の辺を張る // このとき to から from へも容量 0 の辺を張っておく void addedge(int from, int to, int cap) { int fromrev = (int)list[from].size(); int torev = (int)list[to].size(); list[from].push_back(Edge(torev, from, to, cap)); list[to].push_back(Edge(fromrev, to, from, 0)); } }; struct FordFulkerson { static const int INF = 1 << 30; // 無限大を表す値を適切に vector<int> seen; FordFulkerson() { } // 残余グラフ上で s-t パスを見つける (深さ優先探索) // 返り値は s-t パス上の容量の最小値 (見つからなかったら 0) // f: s から v へ到達した過程の各辺の容量の最小値 int fodfs(Graph &G, int v, int t, int f) { // 終端 t に到達したらリターン if (v == t) return f; // 深さ優先探索 seen[v] = true; for (auto &e : G[v]) { if (seen[e.to]) continue; // 容量 0 の辺は実際には存在しない if (e.cap == 0) continue; // s-t パスを探す // 見つかったら flow はパス上の最小容量 // 見つからなかったら f = 0 int flow = fodfs(G, e.to, t, min(f, e.cap)); // s-t パスが見つからなかったら次辺を試す if (flow == 0) continue; // 辺 e に容量 flow のフローを流す G.run_flow(e, flow); // s-t パスを見つけたらパス上最小容量を返す return flow; } // s-t パスが見つからなかったことを示す return 0; } // グラフ G の s-t 間の最大流量を求める // ただしリターン時に G は残余グラフになる int solve(Graph &G, int s, int t) { int res = 0; // 残余グラフに s-t パスがなくなるまで反復 while (true) { seen.assign((int)G.size(), 0); int flow = fodfs(G, s, t, INF); // s-t パスが見つからなかったら終了 if (flow == 0) return res; // 答えを加算 res += flow; } // no reach return 0; } }; int solve(int M, int N) { vector<int> b(M), c(N); for (int i = 0; i < M; ++i) cin >> b[i]; for (int i = 0; i < N; ++i) cin >> c[i]; Graph G(N + M + 2); int s = N + M, t = N + M + 1; // スーパーノートとつなぐ for (int i = 0; i < M; ++i) { G.addedge(s, i, 1); } for (int i = 0; i < N; ++i) { G.addedge(i + M, t, 1); } // 二部グラフを作る for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (gcd(b[i], c[j]) > 1) { G.addedge(i, j + M, 1); } } } FordFulkerson ff; return ff.solve(G, s, t); } int main() { // 入力 int M, N; while (cin >> M >> N) { if (M == 0) break; cout << solve(M, N) << endl; } }
コード (Hopcroft-Karp による解)
より高速なアルゴリズムによる解法です。
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; struct HopcroftKarp { int sizeL, sizeR; vector<vector<int> > list; // left to right // result vector<bool> seen, matched; vector<int> level, matching; // base HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { } inline vector<int>& operator [] (int i) { return list[i]; } inline void addedge(int from, int to) { list[from].push_back(to); } inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { s << endl; for (int i = 0; i < G.list.size(); ++i) { s << i << " : "; for (int j = 0; j < G.list[i].size(); ++j) { s << G.list[i][j]; if (j + 1 != G.list[i].size()) s << ", "; } s << endl; } return s; } // methods void hobfs() { queue<int> que; for (int left = 0; left < sizeL; ++left) { level[left] = -1; if (!matched[left]) { que.push(left); level[left] = 0; } } level[sizeL] = sizeL; while (!que.empty()) { int left = que.front(); que.pop(); for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] == -1) { level[next] = level[left] + 1; que.push(next); } } } } bool hodfs(int left) { if (left == sizeL) return true; if (seen[left]) return false; seen[left] = true; for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] > level[left] && hodfs(next)) { matching[right] = left; return true; } } return false; } int solve() { seen.assign(sizeL, false); matched.assign(sizeL, false); level.assign(sizeL+1, -1); matching.assign(sizeR, sizeL); int res = 0; while (true) { hobfs(); seen.assign(sizeL, false); bool finished = true; for (int left = 0; left < sizeL; ++left) { if (!matched[left] && hodfs(left)) { matched[left] = true; ++res; finished = false; } } if (finished) break; } return res; } }; int GCD(int a, int b) { return b ? GCD(b, a%b) : a; } int main() { int N, M; while (cin >> N >> M, N) { HopcroftKarp G(N, M); vector<int> left(N), right(M); for (int i = 0; i < N; ++i) cin >> left[i]; for (int i = 0; i < M; ++i) cin >> right[i]; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (GCD(left[i], right[j]) > 1) G.addedge(i, j); } } cout << G.solve() << endl; } }
