1469:COURSES

keyword

2部マッチング　C++

概要

P(<100)個の委員会とN(<300)人の生徒がいる。各委員会にどの生徒が所属しているかという情報が与えられる。このとき、各委員会から重複しないように一人ずつ生徒を選出できるかどうか判定する問題。
生徒と委員会を2部グラフに見立てて2部マッチングの最大個数が委員会の数と一致するか見れば良い。

int main(){
    int rept, P, N, x, pcnt, i, j;
    rept = readint();
    while(rept--){
        P = readint();
        N = readint();
        REP(i,P+N+2) G[i].clear();
        REP(i,P){
            pcnt = readint();
            REP(j,pcnt){
                x = readint();
                G[i+1].push_back((edge){P+x,1,G[P+x].size()});
                G[P+x].push_back((edge){i+1,0,G[i+1].size()-1});
            }
        }
        REP(i,P){
            G[0].push_back((edge){i+1,1,G[i+1].size()});
            G[i+1].push_back((edge){0,0,G[0].size()-1});
        }
        REP(i,N){
            G[P+i+1].push_back((edge){P+N+1,1,G[P+N+1].size()});
            G[P+N+1].push_back((edge){P+i+1,0,G[P+i+1].size()-1});
        }
        if(P==max_flow(0,P+N+1)) puts("YES");
        else puts("NO");
    }
    return 0;
}