典型的な二部マッチングの問題です。
問題へのリンク
問題概要
枚の赤いカードと、
枚の青いカードとの間でマッチングを作っていきます。
各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。
最大マッチングのサイズを求めてください。
考えたこと
二部グラフを作って、二部マッチングアルゴリズムで解くことができます。ここでは
- スーパー頂点
を追加して、最大流アルゴリズム Ford-Fulkerson 法のよる実装
- 二部マッチング専用の高速アルゴリズム Hopcroft-Karp 法による実装
を示します。
コード (Ford-Fulkerson 法による解)
#include <bits/stdc++.h>
using namespace std;
struct Graph {
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;
Graph(int N = 0) : list(N) { }
size_t size() {
return list.size();
}
vector<Edge> &operator [] (int i) {
return list[i];
}
Edge& redge(const Edge &e) {
return list[e.to][e.rev];
}
void run_flow(Edge &e, int f) {
e.cap -= f;
redge(e).cap += f;
}
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() { }
int fodfs(Graph &G, int v, int t, int f) {
if (v == t) return f;
seen[v] = true;
for (auto &e : G[v]) {
if (seen[e.to]) continue;
if (e.cap == 0) continue;
int flow = fodfs(G, e.to, t, min(f, e.cap));
if (flow == 0) continue;
G.run_flow(e, flow);
return flow;
}
return 0;
}
int solve(Graph &G, int s, int t) {
int res = 0;
while (true) {
seen.assign((int)G.size(), 0);
int flow = fodfs(G, s, t, INF);
if (flow == 0) return res;
res += flow;
}
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;
vector<bool> seen, matched;
vector<int> level, matching;
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;
}
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;
}
}
