SRM 658 div1 hard:DancingForever

Dancing・Forever。

問題

解法

kmjpさんの記事を参考にさせていただきました。<a href="http://kmjp.hatenablog.jp/entry/2015/05/17/0930">TopCoder SRM 658 Div1 Hard DancingForever - kmjp's blog</a>kmjp.hatenablog.jp

なんでこの解き方で良いかについて少し補足しようと思います(ちょっと自分でもあってるか心配ですが…)。

kmjpさんの解説にあるように,結局は最大マッチングで得られた残余グラフについて,sourceから到達できる頂点を選んできて,それについて再び最大マッチングをかけると,条件を満たすようになっているということですね。

これはなぜなのか,ということを詳しく考えてみます。このことを示す前にとりあえず言葉の定義です。

・残余グラフでsourceから到達することのできる男性の集合をBとする。
・残余グラフでsourceから到達することのできる女性の集合をGとする。

さて,問題を示すために必要なことは以下の2つに分けることが出来ます。

①Bの各人はG外の女性に対して好意を持っていない(このことによって,Gの要素すべてがマッチングされたとするとそれは条件を満たしているということが示される)
②2回目に作ったグラフの最大マッチングは|G|である
　　これが決定的ですね。Hallの定理から導かれます。

①,②を用いるとkmjpさんの示している解き方で正しいことが示されます。…ということで示していきましょうか…

①
背理法で示します。
あるg $\notin$ Gについて,b $\in$ Bから線が引かれていたとすると,

b -> g

について,bは到達可能でgは到達不可能であることになる。これは明らかに矛盾している。なぜなら,bが到達可能でgに向かって矢印が引かれているので,gも到達可能でGに含まれるはずだから。

②
これが難しいですね。今は矢印がBの方からGの方に向かって引かれていますが,マッチングする際はそれはどちら向きに引かれていても問題にはならないのでGの方からBの方に向かって矢印が引かれていると考えても問題ありません。
このように考えると,②を示すには,Gの頂点をすべてカバーするマッチングが存在することを示せば良いことになるので,これにはHallの定理が使えます。
すなわち,任意のGの部分集合Aについて, $|A| \leq |\Gamma(A)|$ が示されれば良いです。

これを背理法で示します。
仮にGの部分集合Aの中で $|A| > |\Gamma(A)|$ となるものが存在したとすると,以下のようにして矛盾が示せます。

この場合は例えば図のように辺が貼られていることになります。
f:id:mayokoex:20150521203017p:plain
今選ばれている頂点はsとtについて最小カットを考えた時s側に入っている頂点の集合になります(これは最大フローと最小カットが一致していることの証明で使われているテクニックです。ちょっと良く知らないという人は最大フローと最小カットが一致することの証明を読んでみてください)。
今考えているグラフでは最小カットを定める頂点の集合は{s, b1, b2, g1, g2, g3}となっているので,最小カットは3ということになっています(g1->t, g2->t, g3->tの3つ)。
しかし,カットを決める時sだけをs側の集合とすればカットはs->b1とs->b2の2つだけになり,先ほど考えた集合は最小カットになっていないとわかります。これは最小カットの最小性に矛盾しています。

今考えたことは簡単に一般化出来ます( $|A| > |\Gamma(A)|$ なのでs側だけに頂点集合を集めればカット数が $|A|$ から $|\Gamma(A)|$ に減少し,最小カットでないとわかる,という流れ)。よって, $|A| > |\Gamma(A)|$ となるものが存在しないとわかります。以上により,②を示すことが出来ました。

以下ソースコード

template<class T>
class FordFulkerson {
public:
    struct edge{
        int to;
        int rev;
        T cap;
        edge() {}
        edge(int t, int r, T c) : to(t), rev(r), cap(c) {}
    };
    static const int MAXV = 10000;
    vector<edge> E[MAXV];
    int vis[MAXV];
    void add_edge(int x, int y, T cap, bool undir = false) {
        E[x].push_back(edge(y, E[y].size(), cap));
        E[y].push_back(edge(x, E[x].size()-1, undir?cap:0));
    }
    T dfs(int from, int to, T cf) {
        T tf;
        if (from == to) return cf;
        vis[from] = 1;
        for (auto &e : E[from]) {
            if (vis[e.to] == 0 && e.cap > 0) {
                tf = dfs(e.to, to, min(cf, e.cap));
                if (tf > 0) {
                    e.cap -= tf;
                    E[e.to][e.rev].cap += tf;
                    return tf;
                }
            }
        }
        return 0;
    }
    T maxFlow(int s, int t) {
        T flow = 0, tf;
        while (1) {
            memset(vis, 0, sizeof(vis));
            tf = dfs(s, t, numeric_limits<T>::max());
            if (tf == 0) return flow;
            flow += tf;
        }
    }
};

const int MAXN = 300;
int vis[MAXN];
void dfs(int v, FordFulkerson<int>* ff) {
    vis[v] = 1;
    for (auto e : ff->E[v]) {
        if (vis[e.to] == 0 && e.cap > 0) dfs(e.to, ff);
    }
}

class DancingForever {
public:
    vector <int> getStablePairs(string x) {
        int n = 0;
        {
            int tmp = x.size();
            while (1) {
                if (n*n >= tmp) break;
                n++;
            }
        }
        FordFulkerson<int> *ff1 = new FordFulkerson<int>();
        FordFulkerson<int> *ff2 = new FordFulkerson<int>();
        {
            int s = 2*n+3;
            int t = s+1;
            for (int i = 0; i < n; i++) {
                ff1->add_edge(s, i, 1);
            }
            for (int i = 0; i < n; i++) {
                ff1->add_edge(n+i, t, 1);
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (x[i*n+j] == 'Y') ff1->add_edge(i, j+n, INF);
                }
            }
            int f = (ff1->maxFlow(s, t));
            cout << f << endl;
            memset(vis, 0, sizeof(vis));
            if (f == n) {
                for (int i = 0; i < n; i++) {
                    vis[i] = vis[i+n] = 1;
                }
            } else {
                dfs(s, ff1);
            }
        }
        vector<int> ans;
        {
            int s = 2*n+3;
            int t = s+1;
            for (int i = 0; i < n; i++) {
                if (vis[i]) ff2->add_edge(s, i, 1);
            }
            for (int i = 0; i < n; i++) {
                if (vis[i+n]) ff2->add_edge(i+n, t, 1);
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (x[i*n+j] == 'Y' && vis[i]) ff2->add_edge(i, j+n, 1);
                }
            }
            int f = ff2->maxFlow(s, t);
            for (int i = 0; i < n; i++) {
                if (!vis[i]) continue;
                for (auto e : ff2->E[i]) {
                    if (vis[e.to] && e.cap == 0 && e.to != s) {
                        ans.push_back(i);
                        ans.push_back(e.to-n);
                    }
                }
            }
        }
        return ans;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 658 div1 hard:DancingForever

問題

解法