WARush

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

SRM581 Div2 Hard "TreeUnionDiv2"

問題

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

マナオはグラフの性質、特に単純な閉路について勉強している。頂点がv0, v1, v2... vグラフGにおける長さL(3以上)の単純な閉路とは次のような感じだ。
f:id:Ekaing:20130616132648j:plain

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

マナオは、最適なPを生成したとき、2つの木を結合して出来たグラフで、長さKの閉路を最大何個出来るかを知りたい。

あなたは2つのString[]s tree1とtree2が与えられる。どちらもN個のの要素を持っており、どれもN文字の長さの文字列である。頂点iとjが繋がっていたら、i番目の文字列のj番目の文字は'X'となっており、そうでなければ'-'となっている。

長さKの閉路の最大数を返せ。

制約

1 <= N <= 9
3 <= K <= 7



考えた事

実際に全ての順列Pを生成し、シミュレートしていくぅ
tree1の任意の2つの頂点を使ってKが出来た分だけ答えをたしていくぅ
2つの頂点のパスの長さが必要なので、ワーシャルフロイドで出しておくぅ
各Pで最大をとっていくぅ
計算量は9! * 9 * 9で3000万ほどに収まっているぅ

事後

総当りだし、Mediumより考えは簡単?


ソースコード

vector<string> tree1, tree2;
int d1[9][9], d2[9][9];
int n, k;
int ans;

class TreeUnionDiv2 {
public:

    void rec(){
        
        int t2[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        // 順列で回す
        do{
            int res = 0;
            // 任意の2頂点で回す
            for( int t1_s = 0; t1_s < n; t1_s++ ){
                for( int t1_t = t1_s + 1; t1_t < n; t1_t++ ){
                    int t2_s = t2[t1_s], t2_t = t2[t1_t];
                    if( d1[t1_s][t1_t] + d2[t2_s][t2_t] + 2 == k ) res++;
                }
            }
            ans = max( ans, res );

        }while( next_permutation(t2, t2 + n) );
    }

    int maximumCycles(vector <string> _tree1, vector <string> _tree2, int K){
        tree1 = _tree1;
        tree2 = _tree2;
        n = tree1.size();
        k = K;

        // 距離を出す
        const int INF = 1000;
        for( int i = 0; i < n; i++ ){
            for( int j = i + 1; j < n; j++ ){
                if( tree1[i][j] == 'X' ){
                    d1[i][j] = d1[j][i] = 1;
                }else{
                    d1[i][j] = d1[j][i] = INF;
                }
                if( tree2[i][j] == 'X' ){
                    d2[i][j] = d2[j][i] = 1;
                }else{
                    d2[i][j] = d2[j][i] = INF;
                }
            }
        }

        // ワーシャルたん
        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] );
                }
            }
        }

        ans = 0;
        rec();
        return ans;
    }
};