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; } };