WARush

SRMの結果とか、解けた問題のコードを書いていきます

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



考えた事

紙に書いて試してみると、既にオンになっているところをわざわざオフにしてまでやっても、回数を減らす効果は無いことがうっすら分かった。

・・しかし実装できず。


解法

こちらを参考にしましたm(_ _)m
SRM 583 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ


他人のブログに解説を委ねていくスタイル


ソースコード

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