SRM581 Div1 Medium "TreeUnion"

問題

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

訳

マナオはグラフの性質、特に単純な閉路について勉強している。頂点がv0, v1, v2... vグラフGにおける長さL（３以上）の単純な閉路とは次のような感じだ。

マナオは２つの木をつなげたようなグラフに興味がある。繋げかたは、次のようにする。まず、N個の頂点を持つ２つの木を用意する。２つの木の各頂点に0～N-1の番号を振る。それから、0～N-1の順列 Pを作る。最後に、i～N-1の各iについて、１番目の木のi番目の頂点と、２番目の木のP[i]番目の頂点を繋げる。

マナオは、Pをランダムに生成したとき、２つの木を結合して出来たグラフで、長さKの閉路を出来る数の期待値を知りたい。

-- 入力の形式は割愛 --

長さKの閉路の数の期待値を返せ。

制約

1 <= N <= 300
3 <= K <= 7

解法

コチラ以上に詳しいところはありますまい
TopCoder SRM 581, Division 1, Level 2 : TreeUnion - torus711のアレ

ソースコード

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