読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

TCO 2015 Round 1A Hard - Revmatching

programming SRM

問題

TopCoder Statistics - Problem Statement

問題概要

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

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

イデア

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

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

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

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

実装(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;
    }
};