kojingharangの日記

2015 TCO Round1A 1000 Revmatching

10:38 |

• N頂点-N頂点 の重み付き２部グラフが与えられる。完全マッチングにならないように辺を減らしたい。消す辺の重みの合計の最小値を求めよ。
• 1≦N≦20, 0≦重み≦9

• 左右のどれかの頂点を完全に孤立させれば少なくとも完全マッチングにはならんだろう
• 十分か分からないけど他に思いつかないので書いてみる→最後のサンプルでだめ
• ググるもいまいちそれっぽいのが出ず。
• フロー？
• 片側の頂点数 20 だから部分集合総当り？

• (あとで)
• Hall の定理を使うらしい。
• 任意の左の頂点部分集合 L に対応する右の頂点集合 R が |L|≦|R| ←→完全マッチングが存在する
• ある L について |L|＞|R| になればいいので、
• 部分集合それぞれについて、|L|＞|R|になるように R につながる辺を消した時の最小コストを求めてその最小値を返せばよい。
• ほー、覚えておこう。

• Accepted in practice

class Revmatching {
public: 
	int smallest( vector <string> A ) { 
		ll N = A.size(); 
		ll ans = 1000000; 

		RANGE(b, 1, 1<<N) {
			VI rmCosts(N); 
			// li ... left index  ri ... right index
			REP(li, N) if(b>>li&1) REP(ri, N) rmCosts[ri] += A[li][ri]-'0'; 
			sort(ALL(rmCosts));
			ll nL = POPCOUNT(b); 
			ll rmCost = 0;
			// rm R nodes as little as possible so that |L|>|R|, which means |L|-1 = |R|
			REP(i, N - (nL-1)) rmCost += rmCosts[i];
			ans = min(ans, rmCost); 
		} 
		return ans; 
	}
}; 

ツイートする