Codeforces Round #709 Div.1A. Basic Diplomacyを二部グラフの最大マッチングで解く ACL利用 (最大流/maxflow)

貪欲で解けるが、ACLを使った２部マッチングで解きます。ACLでの復元を行います。

題意

• n人の友達と、m日の遊びたい日があります
• i日目に遊べる友達は$a_1, a_2..a_k$ さん。という情報が与えられます
• あなたは毎日誰か１人のみと遊びたいです。別の日に同じ友人と遊んでも良いです。m日の間に遊ばない友達がいても良いです。
• ただし、ある友人と遊ぶ回数が$ceil(\frac{m}{2})$を超えてはいけないです
• 0人と遊ぶ(つまり誰とも遊べない)日があってはなりません。
• これが達成できる場合、その例を１つ挙げてください。無理なら、NOと答えてください。

方針

n人, m日とstart, end のノードs,t分のn+m+2の点を用意します。
辺の張り方は以下の通りです。

• sから各人に対して$cap = ceil( \frac{m}{2})$の辺を張ります。これは、あなたは各人にこれ超える回数遊ぶことはできないという制約になります。
• 各人から選択できる各日に対して$cap = 1$の辺を張ります。各人はあなたと遊ぶ最大の回数内($=ceil( \frac{m}{2})$)で日を選ぶことができます。
• 各日からtに対して$cap = 1$の辺を張ります。これによって、複数の人からこの日が選ばれることがなくなります。(人1と人2から日1が選ばれてしまっても日1からゴールへは1しか流せないので、どちらかは0でないといけません。)
  この上で、sからtに最大流を流します。この最大流をmfとします。

mfは条件下で遊べる最大の日数になります。このため、$mf=m$でないとき、NOです。$mf=m$であるとき、現在、流せているフローが答えです。これを満たす条件を出力します。

n=4, m=6の時のグラフの例を示します。

復元

以下はACLの例を示します。

さて、流せたと気温このグラフの復元を考えます。ACLをはじめ、最大流のアルゴリズムはmaxflowを達成した瞬間の各辺の流量を保持しています。

今回の問題の場合、人から日につないだcap=1の辺にフローが流れていればその日はその人を使うことになります。各日はtに対してcap=1しか持たないため、複数の人からある日に対してフローが流れることはありません。

ACLでは、現在の辺の状況について、以下の２つの種類のクエリを発行できます。全部でn本の辺を追加したとすると(以下、iは0-indexedとします。)

• i番目に追加した辺をedge get_edge(x)で得る
• 追加された純のすべての辺 n個の要素からなるvector edges()で得る

今回は後者のedges()を使います。

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

edgesは次の4つの変数を持ちます。

• from, to, cap:　入力された点と流せる流量
• flow: 最大流の際に流れている流量

(ACLの)mfの辺の取得は少しコツが要ります。上記の結果は辺が追加されたに格納されています。このため、例えば、点3から張られているすべての辺の情報を見たいといった場合は、各点ごとの追加された辺を覚えていく必要があります。
さて、コードを振り返ると、今回は日ごとに順に候補となる人を選びました。そのため、すべての辺を見ていき、人と日をつなぐ辺（つまり、始点あるいは終点をfrom, toに含まない）で、flow=1が流れている点を順に選んでいけば、題意とグラフの作り方から、誰を選んでいけばいいかがわかることになります。
※丁寧に判断するなら、flow = 1 の時、to日目は人fromにすればよいです。

実装

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