Problem 1163 : Cards

AOJ ICPC

keyword

2部グラフ　マッチング　C++

概要

数列a_iとb_iが与えられる。a_iとb_jは互いに素でなければペアとして選ぶことができる。最大でいくつペアをつくることができるか求める問題。
2部グラフの例題のような問題で動作確認にありがたい問題。

int main(){
    int m, n, i, j;
    int blues[502], reds[502];

    while(scanf("%d%d",&m,&n)){
        if(!(n||m))break;
        REP(i,m)scanf("%d",blues+i);
        REP(i,n)scanf("%d",reds+i);
        vector< vector<int> > bigraph(m);
        REP(i,m)REP(j,n)if(__gcd(blues[i], reds[j]) > 1)
            bigraph[i].PB(j);
        printf("%d\n", BipartiteMatchingByList(bigraph));
    }

    return 0;
}