1163 Cards
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1163
方針
明らかに2部グラフのマッチングに見える。
ソース
#include<iostream> #include<vector> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define REP(i,a,b) for(i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) int b[501],r[501],m,n; vector<int> G[1001]; int gcd(int x,int y) { if(y == 0) return x; return gcd(y,x%y); } bool bfs(vector<int> &pair_v,vector<int> &dist) { queue<int> Q; const int NIL = n+m; fill(dist.begin(), dist.end(), 1<<29); for(int i=0; i<n+m; ++i) if(pair_v[i] == NIL) { dist[i] = 0; Q.push(i); } while(!Q.empty()) { int v = Q.front(); Q.pop(); if(v != NIL) { for(int i=0; i<G[v].size(); ++i) { if(dist[pair_v[G[v][i]]] == 1<<29) { dist[pair_v[G[v][i]]] = dist[v]+1; Q.push(pair_v[G[v][i]]); } } } } return dist[NIL] != 1<<29; } bool dfs(int v,vector<int> &pair_v,vector<int> &dist) { const int NIL = n+m; if(v != NIL) { for(int i=0; i<G[v].size(); ++i) { int u = G[v][i]; if(dist[pair_v[u]] == dist[v]+1) { if(dfs(pair_v[u],pair_v,dist)) { pair_v[u] = v; pair_v[v] = u; return true; } } } dist[v] = 1<<29; return false; } return true; } int biparate_matching() { vector<int> pair_v(n+m+1, n+m); // NIL == n+m vector<int> dist(n+m+1); int matching = 0; int bc = 0; while(bfs(pair_v,dist)) { bc++; for(int i=0; i<n+m; ++i) { if(pair_v[i] == n+m) if(dfs(i,pair_v,dist)) { matching++; } } } return matching; } int main() { int i,j; while(cin>>m>>n, m|n) { rep(i,m) cin>>b[i]; rep(i,n) cin>>r[i]; rep(i,n+m) G[i].clear(); rep(i,m) rep(j,n) { if(gcd(b[i],r[j]) > 1) { G[i].push_back(j+m); G[j+m].push_back(i); } } cout<<biparate_matching()<<endl; } }