1484_2c.cpp

gistfile1.txt

#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
using namespace std;
using namespace atcoder;
const int numNode = 2*100000;
const int numColor = 4 * 100000;
const int numGraph = numNode + numColor + 100;
const int snode = numGraph - 3;
const int tnode = numGraph - 2;
#define ceil(a,b) ((a) + ((b) - 1)) / (b)

int solve(){
    int n, m;
    cin >> n>>m;
    mf_graph<int> mf(1 + n + m + 1); // n+m + s,tのノードを作る
    int x, y;
    // スタートノードから人に対して割り当てていい最大数を春
    REP(i, n) mf.add_edge(0, i+1, ceil(m, 2));
    REP(i, m){
        // 日からゴールにcap1だけをはる
        mf.add_edge(n+i+1, n+m+1, 1);
        cin >> x;
        REP(j, x){ // その日に対して
            cin >> y; // アサインできる人は
            mf.add_edge(y , i+1+n, 1); // 1を張ってもよい
        }
    }
    auto maf = mf.flow(0, n+m+1);
    // tに m 流れない場合、これは見たせない
    if(maf != m){ cout << "NO" << "\n"; return 0; }
    cout << "YES" << "\n";
    vector<mf_graph<int>::edge> edges = mf.edges();
    vector<int> res;
    for (auto &e : edges) { // 全部の辺を見て
        if(e.from == 0) continue; // sからは無視
        if(e.to == n+m+1) continue; // t へも無視
        if(e.flow == 1) res.emplace_back(e.from); // 制約的に日->tはcap1なのでこれでよい
        // 本来は、e.to に対するfromを知りたいのでそう書いた方がよいかも
    }
    REP(i, m-1) cout << res[i] << " ";
    cout << res[m-1] << "\n";
    return 0;
}

int main(int argc, char *argv[]) {
    int q;
    cin >> q;
    REP(i, q) {
        //cout << i << "--"<<"\n";
        solve();
    }
}