TCO 2015 Round 1A Hard - Revmatching

問題

TopCoder Statistics - Problem Statement

問題概要

重み付き2部グラフが与えられる。それぞれのグループに対して、頂点数が個ある(つまり、グラフの頂点数は合計で個)。そして、次の正方行列が与えられて、は片方のグループの頂点からもう片方のグループの頂点へ重みの辺が張られていることを表す。もしの値がの時には、辺は張られていないと考える。の値が'1'~'9'の間の値の時には、その重みの辺が張られていることを表す。

何本か辺を削除することによって、この2部グラフの完全マッチングをなくしたい。この時に、削除する辺の重みの合計の最小値を求めよ。

アイデア

問題から見ても明らかなように、2部グラフのマッチングの問題。マッチングの問題は全然解いたことないので糸口も見つからなかった。

そもそも、与えられる2部グラフから完全マッチングを作れるのかどうかということを知る必要がある(出来ないとわかれば答えは0で良い)。これについては、まさにホールの定理として解決される。ここで言われている近傍というのは、その頂点集合に隣接している頂点集合ということらしい。このへんの記事が分かりやすかった(http://mathtrain.jp/hall)。

この考えを基にしていく。片方の集合をとし、もう片方をとする。の部分集合に対して、その近傍をとする(ここにはグラフの性質上、の頂点集合が入る)。完全マッチングが存在するということは、つまり任意のの部分集合に対して、が成り立つことが条件となる。つまり、完全マッチングがなくなるようにしたいこの問題においては、否定を取って「の部分集合のうち、少なくとも１つはを満たす部分集合が存在する」ということになる。条件より、なので、部分集合を全列挙しても十分間に合うだろう。

では、部分集合を固定する。ある部分集合に対して、前述のとおり、はの部分集合になる。この部分集合に対して、いくつかの辺を削除してとなるようにする。そのコストの最小化を考えてみる。内のある頂点をこの集合から除外するためのただ1つの方法は、からへと繋がる全ての辺を切ることである。内のある頂点に対して、これらはで計算可能。つまり、内の頂点全てに対しては、となる。となるようにするために個の頂点を選ばなければいけないとなった場合には、少ない方から個を選んであげるのが最適となる。

実装(C++)

class Revmatching {
    public:
    int smallest(vector<string> A) {
        int n=A.size();
        int ret=10000000;

        vector<int> cost(n);
        //部分集合を選ぶ
        for(int p=1; p<1<<n; ++p)
        {
            //集合Yの頂点iを取り除くのに必要なコストを計算
            //iが部分集合pのどの頂点とも繋がっていなければcost=0
            rep(i,n)
            {
                cost[i]=0;
                //iにつながっている部分集合内の頂点を探す
                rep(j,n)
                {
                    if(p>>j&1) cost[i]+=A[j][i]-'0';
                }
            }

            //部分集合pのサイズ
            int s=__builtin_popcount(p);
            //取り除くべき頂点数
            int r=n-s+1;

            sort(all(cost));
            int t=0;
            rep(i,r) t+=cost[i];
            ret=min(ret,t);
        }

        return ret;
    }
};