GCJ 2016 Round 1B C - Technobabble

問題

Dashboard - Round 1B 2016 - Google Code Jam

問題概要

先生が学会での発表者を募集している．参加したい生徒たちが発表のタイトルを英単語2つで紙に書いていく．ただし，既に書かれているタイトルは書いていけない(同じタイトルはダメ)．締め切りの後で，それらはランダムな順番に並び替えられる．

生徒の中には学会で出る軽食が美味しいからといって参加しようと思っている者(fakerと呼ぶ)がいる．そういう人は，既に紙に書いてある1単語目と2単語目を選んで組み合わせてトピックを紙に書いている．このとき，1単語目は1単語目にしか，2単語目は2単語目にしか選ばない(例えば，いまapple juiceとorange iceというトピックが有る時，fakerはapple iceやorange juiceといったトピックを作る．juice iceのように，もともとjuiceが2単語目なのに1単語目として選ばれることはない)．これは書いた後でランダムな順番に並び替えられるので，これが完全にfakerによるものだということが見抜けなくなってしまうのだ．

個のタイトルが書かれた並び替えられた後のリストが与えられる．fakerが書いたトピックとしてあり得る数の最大値を答えよ．

アイデア

まず，smallはである．これはどれがfakerが作成したトピックであるかを全探索することで最大値を求められる(通り)．fakerが作成したトピックを仮定すると，残りは本物ということになる．その本物の中からfakerが作ったとされるトピックが作れるかどうかを判定して，全て作れる時はその個数の最大値を更新すればよい．

largeはである．この問題は1つ目の単語と2つ目の単語を結んだグラフとして考えるとわかりやすい．これらは1つ目の単語同士，2つ目の単語同士をつなぐ辺は絶対にないのでこのグラフは二部グラフになる．そして，今求めたいものは「最小辺カバー」と呼ばれるものである．これは蟻本に書かれているが，まず辺カバーとは辺の全体の部分集合に対して，グラフのどの頂点も少なくとも1つに属する辺に接しているということを指す．

また，「グラフに孤立点がなければ」，最大マッチングと最小辺カバーには次のような関係がある．

これは最大マッチングが出来た状態を考えてみると，その時点で辺の本数は本になっていて，マッチングはその辺の端点を共有しないのでその時点で辺に接している頂点が個あることになる．すると，今辺に接していない頂点の数は個存在し，これらを効率よく繋ぐ方法を考えてみる．しかしながら，最大マッチングに含まれていない頂点同士を繋ぐような辺はグラフに存在しない(このような辺があるなら最大マッチングの条件を満たさない)ので，これらの頂点を含むために本の辺を新たに選ぶ必要があるわけである(孤立点がないので，このような辺は存在する)．よって，立式するととなり，関係を示せた．

というわけで，この問題は最大マッチングを求める問題に帰着できる．二部グラフの最大マッチングは，フローによって求めることができる．

そして，その最小辺カバーが求まれば，その辺だけを使うことによって全ての本物のトピックを作り，それ以外はfakerのものであると断定してしまうことが出来るので，リストの数から最小辺カバーを引いた値が解となる．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

//SETTING

//型設定(int?long?ll?)
typedef int ff_t;

//辺を表す構造体(行き先、容量。逆辺)
struct edge {ff_t to, cap, rev;};

//ノードの数
const ff_t MAX_V = 2010;
//LIMIT
const ff_t FF_INF = 123456;
//グラフの隣接リスト表現
vector<edge> G[MAX_V];
//DFSですでに調べたかのフラグ
bool used[MAX_V];

//fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(ff_t from, ff_t to, ff_t cap=1){
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size()-1});
}

//増加パスを探す
ff_t ff_dfs(ff_t v, ff_t t, ff_t f){
    if(v==t) return f;
    used[v]=true;

    for(ff_t i=0; i<G[v].size(); ++i){
        edge &e=G[v][i];
        if(!used[e.to] && e.cap>0){
            ff_t d = ff_dfs(e.to, t, min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }

    return 0;
}

//sからtへの最大流を求める
ff_t max_flow(ff_t s, ff_t t){
    ff_t flow=0;
    for(;;){
        memset(used,0,sizeof(used));
        ff_t f = ff_dfs(s,t,FF_INF);
        if(f==0) return flow;
        flow+=f;
    }
}

typedef pair<string,string> ps;

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        //initialize
        rep(i,MAX_V)
        {
            G[i].clear();
            used[i]=false;
        }

        int n;
        cin >>n;

        set<string> F,S;
        vector<ps> w(n);
        rep(i,n)
        {
            cin >>w[i].fi >>w[i].se;
            F.insert(w[i].fi);
            S.insert(w[i].se);
        }

        int a=F.size(),b=S.size();
        /*
        頂点番号
        0:source
        1~a:1番目の単語
        a+1~a+b:2番目の単語
        a+b+1:sink
        */

        //単語と頂点番号のひも付け
        map<string,int> df,ds;
        int ct=1;
        for(const auto& x:F) df[x]=ct++;
        for(const auto& x:S) ds[x]=ct++;

        //辺を張る(容量は全て1)
        //sourceから1番目の単語へ
        for(int i=1; i<=a; ++i) add_edge(0,i);
        //2番目の単語からsinkへ
        for(int i=a+1; i<=a+b; ++i) add_edge(i,a+b+1);
        //1番目の単語から2番目の単語へ
        rep(i,n) add_edge(df[w[i].fi],ds[w[i].se]);

        int min_cov=a+b-max_flow(0,a+b+1);
        int ans = n-min_cov;
        printf("Case #%d: %d\n", t+1, ans);
    }
    return 0;
}