탐욕은 풀 수 있지만, ACL의 2부 일치해를 사용했다.ACL을 통해 복원합니다.

제목의 뜻

친구 n명과 m일 놀고 싶은 날이 있다

다음날 놀 수 있는 친구는 $a1, a_2..a_선생님.이러한 정보가 제공됨

너는 매일 한 사람과만 놀고 싶어.다른 날 같은 친구와 놀 수 있다.한 친구가 이틀 안에 놀지 않아도 된다.

단, 어떤 친구와 노는 횟수는 $cell(\rac{m}{2})달러

를 초과할 수 없습니다.

0명과 놀 날이 있을 수 없다.

달성할 수 있다면 예를 들어 보세요.만약 안 된다면 NO라고 대답해 주세요.

방침.

n인, m일과 start,end의 노드 s,t분의 n+m+2점을 준비합니다.
가장자리를 붙이는 방법은 다음과 같다.

s부터 모든 사람에게 $cap=ceil(\rac{m})$의 가장자리를 붙인다.이것은 네가 너무 많이 놀면 안 되는 횟수를 제한하는 것이다.

모든 사람이 선택할 수 있는 하루에 $cap=1달러의 가장자리를 붙인다.모든 사람이 당신과 놀 수 있는 최대 횟수 (=$cell (\rac {m}) $) 에서 날짜를 선택할 수 있습니다.

매일 t에 $cap=1달러의 테두리를 붙인다.이렇게 되면 많은 사람들이 이 날을 선택하지 않을 것이다.(사람1과 사람2가 1일을 선택하더라도 매일 1에서 종점까지 1일만 흐르기 때문에 0이어야 한다.)
이 기초 위에서 s에서 t로 가장 큰 흐름이 흐른다.이 최대 흐름을 mf로 한다.

mf는 조건하에서 놀 수 있는 최대 일수입니다.따라서 $mf=m달러가 아닌 경우 NOmf=m달러라면 지금 재생하는 절차가 답입니다.나는 이 조건을 만족시키기 위해 수출했다.
n = 4, m = 6시 차트의 예.

되살리다

다음은 ACL의 예입니다.
그렇다면 흐르게 하려면 기온이라는 도표의 복원을 고려해야 한다.ACL을 비롯한 최대 데이터의 알고리즘은 maxflow를 달성하는 순간 각 변의 데이터를 유지하고 있다.
이번 문제에서 사람과 하늘이 이어진cap=1의 흐름이 있다면 그날은 그 사람을 사용해야 한다.매일 t에 대해cap=1만 가지고 있기 때문에 여러 사람에 대한 하루는 흐르지 않는다.
ACL은 다음 두 가지 유형의 질의를 게시할 수 있습니다.총 n 개의 변이 증가하면 (아래 i는 0-indexed)

i번째 추가된 테두리를 edgeget으로 설정edge(x)를 통해 획득

순수한 모든 변 n개 원소를 첨가한vectoredges()를 통해

이번에는 후자의 edges ()를 사용합니다.

vector<mf_graph<int>::edge> edges = mf.edges();
for (auto &e : edges) { ...}

edges는 다음과 같은 네 가지 변수를 가지고 있다.
-from, to,cap: 입력점과 유동량
-flow: 최대 유량 시 흐르는 유량
(ACL의) mf 모서리를 얻으려면 약간의 기교가 필요하다.이러한 결과는 추가 모서리에 저장됩니다.따라서 点3から張られているすべての辺の情報を見たい의 경우 각 점의 추가 모서리를 기억해야 합니다.
그럼 코드를 돌이켜보면 이번에는 매일 후보를 뽑겠습니다.따라서 모든 변을 보고 사람과 해를 연결하는 변(즉, 시작점이나 끝점은 from, to에 포함되지 않음)에서 플로우=1로 흐르는 점을 순서대로 선택하면 제목과 도표의 제작 방법에서 누구를 선택해야 좋을지 알 수 있다.
※ 자세히 판단하려면 플로우=1이 되면 to는 다음 날 사람부터 시작한다.

이루어지다

ACL 부분은 생략됩니다.

#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;
#define ceil(a,b) ((a) + ((b) - 1)) / (b)

int solve(){
    int n, m; // 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;
}