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;
    }
}