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を足す } };