SRM583 Div1 Medium "TurnOnLamps"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12606
訳
ゴブルシティは木構造になっている。そこには0からN-1と番号付けられたN個の交差点がある。交差点は任意の2つの交差点で行き来ができるように、N-1個の双方向の道路で繋がれていた。より正確には任意の2つの交差点は一意のパス(道路のシーケンス)で繋がれている。あなたはroad[i]とi+1 (0 <= i <= N-2) の交差点が道路で繋がれているという意味のint[] roadが与えられる。
それぞれの道路にはひとつのランプが設置されている。これらのランプには0からN-2の番号が付けられている。i番目のランプはroads[i]番とi+1番目の交差点を結ぶ道路に設置されている。あなたはi番目の文字が'1'であればi番目のランプがオンに、そうでなければオフになっているという意味のString initStateが与えられる。
今、あなたはランプのコントロール室にいる。ランプを操作する唯一の方法は次のようなものだ。
2つの交差点番号(XとY)をコントロール室のコンピュータに入力すると、コンピューターはXとYのパスの道路のランプ全てを切り替える。(ランプがオンであればオフに、オフであればオンに)あなたは好きなだけこの操作を行う事ができる。
あなたにとっていくつか重要なランプがあった。その情報はString isImportantとして与えられる。i番目の文字が'1'であればi番目のランプは重要であり、'0'であればi番目のランプはそうではないことを表す。
あなたの目的は全ての重要なランプを同時にオンにする事である。目的を果たすための最小の操作回数を返せ。
制約
2 <= N <= 50
考えた事
紙に書いて試してみると、既にオンになっているところをわざわざオフにしてまでやっても、回数を減らす効果は無いことがうっすら分かった。
・・しかし実装できず。
ソースコード
const int NOT_CONNECT = 0; // 繋がってない const int CONNECT = 1; // 繋がってる const int NOT_FLOW = 2; // 流しちゃだめ! const int IMPORTANT = 3; // 重要だから流して! int N; int G[55][55]; int ans; class TurnOnLamps { public: bool rec( int p, int v ){ int cnt = 0; for( int c = 0; c < N; c++ ){ if( G[v][c] == NOT_CONNECT || c == p ) continue; bool add = false; add |= G[v][c] == IMPORTANT; add |= rec( v, c ); if( add ) cnt++; } ans += cnt / 2; if( cnt % 2 && G[v][p] == NOT_FLOW ) ans++; return cnt % 2 && G[v][p] != NOT_FLOW; } int minimize(vector <int> roads, string initState, string isImportant){ N = roads.size() + 1; memset( G, NOT_CONNECT, sizeof(G) ); for( int i = 1; i < N; i++ ){ int j = roads[i-1]; G[i][j] = G[j][i] = CONNECT; if( isImportant[i-1] == '1' ){ if( initState[i-1] == '1' ){ G[i][j] = G[j][i] = NOT_FLOW; }else{ G[i][j] = G[j][i] = IMPORTANT; } } } ans = 0; if( rec( -1, 0 ) ) ans++; return ans; } };