SRM460 Div2 Hard(1000) TheCitiesAndRoadsDivTwo

TheCitiesAndRoadsDivTwo

試合中の正解者無し。与えられた辺を含む全域木は何通りあるかという問題。全域道（こんな用語あるのだろうか？）は何通りかと勘違いしていた。連結している街に同じ数字を割り振って、数字の異なる街に辺を追加していく。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class TheCitiesAndRoadsDivTwo
{
    static const int N = 9;
    int BT( int n, int city[N], int i );
public:
    int find( vector <string> map );
};

int TheCitiesAndRoadsDivTwo::find( vector <string> map )
{
    int n = (int)map.size();

    //  連結している街に同じ数字を割り当てる
    int city[N];
    for ( int i=0; i<n; i++ )
        city[i] = i;

    for ( int i=0; i<n; i++ )
        for ( int j=0; j<n; j++ )
        for ( int k=0; k<n; k++ )
            if ( map[j][k] == 'Y'  &&
                 city[k] > city[j] )
                city[k] = city[j];

    return BT( n, city, 0 );
}

//  i以上の辺を追加してcityを全て連結する場合の数を返す
int TheCitiesAndRoadsDivTwo::BT( int n, int city[N], int i )
{
    //  全ての街が連結されているか調べる
    if ( count( city, city+n, city[0] ) == n )
        return 1;

    //  数字が異なる街を繋ぐ辺を追加
    int r = 0;
    for ( ; i<n*n; i++ )
    {
        int f = i%n;
        int t = i/n;

        if ( f < t  &&  city[f] != city[t] )
        {
            int c[N];
            for ( int j=0; j<n; j++ )
                c[j] = city[j]==city[t] ? city[f] : city[j];

            r += BT( n, c, i+1 );
        }
    }

    return r;
}