TopCoder Open 2012 Round 1A Div1 Hard

問題

n個のバルブとm個のスイッチがある。
それぞれのスイッチがどのバルブにつながっているかは、switchesにより与えられる。


最初、それぞれのバルブはinitial[]の状態となっている。
スイッチを押すと、つながっているバルブの状態のONとOFFが切り替わる。
全てのバルブの状態をOFFにするのに必要な、スイッチを押す回数を求めよ。


ただし、一つのバルブにつながるスイッチは高々2つとする。

制約条件

n, m≦50
一つのバルブにつながるスイッチは高々2つ

方針

あるバルブにつながるスイッチが0個または一つの場合は自明。
バルブにつながるスイッチが二つの場合が問題。


バルブの初期状態がONのとき、つながる二つのスイッチは(押す, 押さない)または
(押さない, 押す)のどちらかで、
バルブの初期状態がOFFのとき、つながる二つのスイッチは(押す, 押す)または
(押さない, 押さない)のどちらかになる。


i番目のスイッチを押すということを、変数xiにtrueを割り当てることとすれば、
これは2-SAT問題(の、trueを最小にする問題)である。


普通の2-SATを解くように、各変数xiがtrueに対応する頂点と、falseに対応する頂点を作って、「ならば関係」がある頂点同士を辺で結んでグラフを作る。


すると、この問題の場合、グラフが無向グラフになっている。


なので、それぞれの連結成分ごとに、割り当ての仕方は2通りしかなく、
2通りのうちtrueの個数が少ないほうを選べばよい。


それぞれの連結成分ごとに割り当ては独立なので、trueの個数が少ない割り当ての仕方を選んでいって、個数を合計すれば答えになる。

ソースコード

int n, m;
bool e[100][100], use[100];

class EllysLights {
	public:
	int getMinimum(string initial, vector <string> switches) 
	{
		memset(e, 0, sizeof(e));
		memset(use, 0, sizeof(use));
		n = initial.size(), m = switches.size();
		
		rep(i,n){
			int cnt = 0, v[2];
			rep(j,m)if(switches[j][i] == 'Y') v[cnt++] = j;
			if(cnt == 0 && initial[i] == 'Y') return -1;
			if(cnt == 1){
				if(initial[i] == 'Y') use[v[0]*2] = 1;
				else use[v[0]*2+1] = 1;
			}
			if(cnt == 2){
				if(initial[i] == 'Y'){
					e[v[0]*2][v[1]*2+1] = e[v[1]*2+1][v[0]*2] = 1;
					e[v[0]*2+1][v[1]*2] = e[v[1]*2][v[0]*2+1] = 1;
				}
				else{
					e[v[0]*2][v[1]*2] = e[v[1]*2][v[0]*2] = 1;
					e[v[0]*2+1][v[1]*2+1] = e[v[1]*2+1][v[0]*2+1] = 1;
				}
			}
		}
		
		rep(i,2*m) e[i][i] = 1;
		rep(k,2*m) rep(i,2*m) rep(j,2*m) e[i][j] |= e[i][k] && e[k][j];
		
		rep(i,2*m) if(use[i]) rep(j,2*m) if(e[i][j]) use[j] = 1;
		rep(i,m) if(use[i*2] && use[i*2+1] || e[i*2][i*2+1]) return -1;
		
		rep(i,m) if(!use[i*2] && !use[i*2+1]){
			int c1 = 0, c2 = 0;
			rep(j,m*2){
				if(e[i*2][j]) c1 += j & 1 ^ 1;
				if(e[i*2+1][j]) c2 += j & 1 ^ 1;
			}
			rep(j,m*2){
				if(c1 <= c2 && e[i*2][j]) use[j] = 1;
				if(c2 < c1 && e[i*2+1][j]) use[j] = 1;
			}
		}
		
		int ans = 0;
		rep(i,m) ans += use[i*2];
		
		return ans;
	}
};