SRM581 Div1 Medium "TreeUnion"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12586
訳
マナオはグラフの性質、特に単純な閉路について勉強している。頂点がv0, v1, v2... vグラフGにおける長さL(3以上)の単純な閉路とは次のような感じだ。
マナオは2つの木をつなげたようなグラフに興味がある。繋げかたは、次のようにする。まず、N個の頂点を持つ2つの木を用意する。2つの木の各頂点に0~N-1の番号を振る。それから、0~N-1の順列 Pを作る。最後に、i~N-1の各iについて、1番目の木のi番目の頂点と、2番目の木のP[i]番目の頂点を繋げる。
マナオは、Pをランダムに生成したとき、2つの木を結合して出来たグラフで、長さKの閉路を出来る数の期待値を知りたい。
-- 入力の形式は割愛 --
長さKの閉路の数の期待値を返せ。
制約
1 <= N <= 300
3 <= K <= 7
ソースコード
int d1[330][330]; int d2[330][330]; int dnum1[330], dnum2[330]; class TreeUnion { public: double expectedCycles(vector <string> tree1, vector <string> tree2, int K){ const int INF = 1000; for( int i = 0; i < 330; i++ ){ for( int j = 0; j < 330; j++ ){ d1[i][j] = d2[i][j] = INF; } } // 入力 int N = 0; string t1; for( int i = 0; i < tree1.size(); i++ ){ t1 += tree1[i]; } istringstream iss1( t1 ); for( int i = 1, j = 0; iss1 >> j; i++ ){ d1[i][j] = d1[j][i] = 1; N = i + 1; } string t2; for( int i = 0; i < tree2.size(); i++ ){ t2 += tree2[i]; } istringstream iss2( t2 ); for( int i = 1, j = 0; iss2 >> j; i++ ){ d2[i][j] = d2[j][i] = 1; } // ワーシャルたん for( int k = 0; k < N; k++ ){ for( int i = 0; i < N; i++ ){ for( int j = 0; j < N; j++ ){ d1[i][j] = min( d1[i][j], d1[i][k] + d1[k][j] ); d2[i][j] = min( d2[i][j], d2[i][k] + d2[k][j] ); } } } // dnum初期化 memset( dnum1, 0, sizeof(dnum1) ); memset( dnum2, 0, sizeof(dnum2) ); for( int i = 0; i < N; i++ ){ for( int j = i + 1; j < N; j++ ){ if( d1[i][j] < INF ) dnum1[d1[i][j]]++; if( d2[i][j] < INF ) dnum2[d2[i][j]]++; } } // リングの出来る数を数える long long div = N * (N - 1); long long total = 0; for( int c1 = 1; c1 < N; c1++ ){ int c2 = K - 2 - c1; if( c2 <= 0 ) continue; total += 2LL * dnum1[c1] * dnum2[c2]; // intだとオーバーフローの危険性あり! } return (double)total / div; } };