TopCoder SRM 589 Div1 Medium GearsDiv1

問題

R, G, Bのどれかの色をした歯車がn個ある。
同じ色をした歯車は、すべて同じ向きに回転している。

歯車のうち、いくつかは噛み合っていて、噛み合っている歯車は必ず反対向きの回転をしている。
同じ色をした歯車同士が噛み合っていることはない。

このとき、すべての歯車が同時に回転するために取り除かなければならない歯車の個数の最小値を求めよ。

制約条件

n≦50

方針

色ごとに回転の向きを決めつける。
すると、噛み合ってはいけない歯車同士のグラフを作ることができる。
このグラフは、元のグラフの辺のうち、同じ向きの歯車同士に張られる辺だけを抽出したグラフ。

このグラフのすべての辺は、どちらかの頂点の歯車を必ず取り除かなければならない。
辺ごとに取り除く頂点を選ぶと考えるとこれは最小点カバー。
したがって、|最大独立集合| + |最小点カバー| = |V|の関係から、
グラフの最大独立集合を求めて、全頂点の数から引いてやればそれが求める答えである。

同じ色の歯車は噛み合っていないという関係を見落としていたのでこういう解法になっているが、この条件を使うともっと実装が楽になる。

まず、三色が同じ回転をしている場合というのは明らかに最適でないので考えなくてよい。
すると、どれか二色の回転が同じになっている。
同じになっている二色の関係を決め打ちして、上と同じ干渉のグラフを作る。

このグラフは異なる二色の頂点間にしか辺がないので二部グラフ。
したがって二部グラフで成り立つ、|点カバー| = |二部マッチング|の関係（koenigの定理）を使えばいい。

ソースコード

独立集合を枝刈りして求めている。最悪ケースが100msくらい。
もう少し枝刈りの実装をまともにすればたぶん最悪10msくらい。

int n, best, deg[50];
bool vis[50], e[50][50];
vi v;
vector<pi> vv;
ll forbid;
int cnt;

void dfs(int c){
	vis[c] = 1;
	vv.pb(mp(-deg[c], c));
	rep(i, n) if(e[c][i] && !vis[i]) dfs(i);
}
void rec(int c){
	best = max(best, cnt);
	if(c == v.size()) return;
	int mx = cnt;
	for(int i = c; i < v.size(); i++) if(!(forbid >> v[i] & 1)) mx++;
	if(mx < best) return;
	
	if(!(forbid >> v[c] & 1)){
		ll pf = forbid;
		rep(i, v.size()) if(e[v[c]][v[i]]) forbid |= 1ll << v[i];
		cnt++;
		
		rec(c+1);
		forbid = pf; cnt--;
	}
	rec(c+1);
}

class GearsDiv1 {
	public:
	int getmin(string color, vector <string> graph) {
		n = color.size();
		int ans = 0;
		
		rep(bit, 4){
			memset(e, 0, sizeof(e));
			memset(vis, 0, sizeof(vis));
			memset(deg, 0, sizeof(deg));
			
			rep(i, n) rep(j, n) if(i == j || graph[i][j] == 'Y'){
				int ci = color[i] == 'R' ? 2 : color[i] == 'G' ? 1 : 0;
				int cj = color[j] == 'R' ? 2 : color[j] == 'G' ? 1 : 0;
				
				if((bit >> ci & 1) == (bit >> cj & 1)){
					e[i][j] = 1;
					deg[i]++;
				}
			}
			
			int tmp = 0;
			rep(i, n) if(!vis[i]){
				v.clear(); vv.clear();
				dfs(i);
				sort(all(vv));
				rep(j, vv.size()) v.pb(vv[j].second);
				
				best = cnt = 0;
				rec(0);
				tmp += best;
			}
			ans = max(ans, tmp);
		}
		return n - ans;
	}
};