TopCoderOpen 2015 Round1A Hard Revmatching

ヒント無しだと解けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13708

問題

2*N頂点の完全二部グラフがある。
N*N本の各辺に対し、辺を取り除くコストが与えられる。

このグラフから、完全マッチングが出来なくなるよういくつかの辺を取り除くことを考える。
取り除く辺の総コストを最小化せよ。

解法

ホールの結婚定理を用いる。

左右N個ずつの頂点をマッチングさせることを考える。
左側のN頂点群のうち、あるx個に対して、それらの右側のマッチング可能な相手の和集合が(x-1)頂点以下なら完全マッチングが成立しない。
よって、右側(N-(x-1))個の頂点を選び、左側x個から右側(N-(x-1))個の頂点へ伸びる辺をすべて削除すればよい。

左側の頂点の選び方はbitmaskを用いて2^N通り総当たりする。
これに対し、右側からどの(N-(x-1))個の頂点を選ぶかが問題となる。
こちらもbitmask総当たりで求めることもできるが、TLEしてしまう。

そこで、右側のN個の頂点yそれぞれに対し、各xからyまでの辺を取り除くコストの和C(mask,y)を求める。
あとはC(mask,y)をソートして小さい順に(N-(x-1))個選べばよい。

class Revmatching {
	public:
	int smallest(vector <string> A) {
		int mat[20][20];
		int N=A.size(),x,y;
		int mi=100000;
		
		
		FOR(x,N) FOR(y,N) mat[x][y]=A[x][y]-'0';
		for(int mask=1;mask<1<<N;mask++) {
			vector<int> V;
			FOR(y,N) {
				int tot=0;
				FOR(x,N) if(mask&(1<<x)) tot+=mat[y][x];
				V.push_back(tot);
			}
			sort(V.begin(),V.end());
			int tot=0;
			FOR(x,N-__builtin_popcount(mask)+1) tot+=V[x];
			mi=min(mi,tot);
		}
		return mi;
	}
}

まとめ

完全マッチングの有無ときたらホールの定理か。