mayoko’s diary

プロコンとかいろいろ。

SRM 557 div1 med Incubator

問題

TopCoder Statistics - Match Overview

DAG が与えられる。次の条件を満たす頂点集合 S の最大の大きさを求めよ。
条件: 任意の異なる 2 つの頂点 i, j  \in S について, i から j へのパスも j から i へのパスもない。

解法

この問題に関して, dilworth の定理というものが知られています。

dilworth の定理
(任意の 2 点間にパスが存在しないような頂点の 部分集合の最大サイズ) = (最小パス被覆の本数)

ここで, パス被覆とは, パスの集合であって, 任意の頂点 v についてあるパス p が存在して v が p に入っているようなものを言います。最小パス被覆は, パス被覆の中で, パスの数が最小のものですね。

(任意の 2 点間にパスが存在しないような頂点の 部分集合の最大サイズ) は問題文に書いた S そのものなので, 結局のところ最小パス被覆の本数が求められれば良くなりました。

で, これに謎の二部グラフを作ると良いのですが, よくわからなかったので twitter に聞いてみたら, Mi_Sawa さんが教えてくれました。

二部グラフの作り方ですが, 頂点集合 V と V' を用意します。そして, もとのグラフで v -> u へのパスが存在する場合, v  \in V から u'  \in V' へ辺を引きます。これで二部グラフは出来上がりです。

で, このようにすると, |V| - (できた二部グラフの最大マッチング) = (最小パス被覆の本数)
となります。理由なんですが, まず, パスの数をなるべく少なくする, ということについて考えます。

パスにある辺の数が e 個であるとすると, それでカバーできる頂点の数は e+1 個です。これを考えると, パス被覆では, (パスの本数) + (パスに使われた辺の本数) = (頂点数) が成り立っていることが分かります。つまり, パスを少なくするためには, なるべく多くの辺を使ってパスの集合を構成すれば良いです。

で, 元のグラフは DAG であることを考えると, 「元のグラフでパスができる」ことと「二部グラフで v  \in V と v'  \in V' の次数は高々 1」であることは同値です。
よって, もとのグラフのパスの集合は二部グラフでマッチングになります。これをなるべく最大化したいので, 最大マッチングを求めれば良いわけですね。

ところで上の説明は微妙に違って, 「元のグラフでのパスの集合」が「二部グラフで v  \in V と v'  \in V' の次数は高々 1 となるもの」が一致しているとは限りません(今回の問題ではサンプル 2 がそういう例になっている)。

ですが, 二部グラフの辺をつなげる条件として 「もとのグラフで v -> u へのパスが存在する」ことを条件にしたので, すでに次数が 1 になっている頂点をパスに含めたいときはそれをパスすれば良いです。こう考えると全部解決ですね。

Dinic のライブラリは省略した解答↓

const int MAXN = 55;
bool can[MAXN][MAXN];

class Incubator {
public:
    int maxMagicalGirls(vector <string> love) {
        memset(can, false, sizeof(can));
        int n = love.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (love[i][j] == 'Y') can[i][j] = true;
            }
        }
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            can[i][j] |= (can[i][k] & can[k][j]);
        }
        const int s = 2*n, t = s+1, V = t+1;
        Dinic dinic(V);
        for (int i = 0; i < n; i++) {
            dinic.add_edge(s, i, 1);
            dinic.add_edge(i+n, t, 1);
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (can[i][j]) {
            dinic.add_edge(i, j+n, 1);
        }
        return n-dinic.max_flow(s, t);
    }
};