WARush

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

SRM570 Div2 Hard " CentaurCompanyDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12426

ある会社はN台のサーバーを持っており、それらは1~Nと番号付けされている。
これらのサーバーは1つのネットワーク内にあり、そのネットワークは木構造になっている。
いいかえれば、ちょうどN-1本の双方向ケーブルがあり、
それぞれがネットワーク全体が接続されるように、2台のサーバーに繋がれている。

この会社はA会社とB会社に分かれることになった。
このことにより、各サーバーをA会社用とB会社用の2つに分けて、
違う会社のサーバーを繋いでいるケーブルは抜く事にした。

B会社は予備のケーブルが沢山あったが、A会社は1つも持っていなかった。
従って、A会社のサーバーを選ぶ時は、既に選んだサーバーのどれかと、
繋がっているようなサーバーでなくてはならない。

それぞれN-1個の整数を持つa, bが与えられる。
これはサーバーa[i]とサーバーb[i]がケーブルで繋がれている事を示す。

サーバーの分け方の数を返せ。(1つの会社が全てのサーバーを持つような分け方も可能)

制約

2 <= N <= 51


ACしてるソースコードをカンニング

dfsで探索していって、
現在探索している頂点を必ず含ませるようなパターン数を計算している。
んで、その数を上に返す前に、上の頂点を全く含まない時の場合の数として、
答えに足しておく。

最後にサーバーを全く使わない場合の1を足す。

ACしてる人数からいくと簡単な方なのかしら・・・


ソースコード

int n;
long long ans;
bool G[55][55];
bool chk[55];

class CentaurCompanyDiv2 {
public:
    // 頂点vを根として、頂点vを必ず含むようなわけ方の数を返す。
    long long dfs( int v ){
        chk[v] = true;
        long long res = 1;
        for( int i = 1; i <= n; i++ ){
            if( chk[i] || !G[v][i] ) continue;
            res = res + res * dfs( i );
        }
        ans += res; // 答えに足しておく
        return res;
    }

    long long count(vector <int> a, vector <int> b){
        memset( G, false, sizeof(G) );
        memset( chk, false, sizeof(chk) );
        
        for( int i = 0; i < a.size(); i++ ){
            G[a[i]][b[i]] = G[b[i]][a[i]] = true;
        }
        n = a.size() + 1;
        ans = 0;
        dfs( 1 );
        return ans + 1; // まったくサーバーを使わない時の1を足す
    }
};