TopCoder SRM 581 Div2 hard TreeUnionDiv2

さてDiv2 Hard。これはDiv1 Mediumを簡単にした問題。
幸いさくっと解法が思いついた。
http://community.topcoder.com/stat?c=problem_statement&pm=12587

問題

最大N点(<=9)からなる同じ点数の木が２つ与えられる。
２つの木の各点をそれぞれ辺でつないで、１つのグラフを作ったとする。
その時、長さKの閉路が最大数できるグラフについて、その閉路の最大数を答える。

解法

K<=7なのがポイント。
２つの木をA,Bとして、Aのある点から閉路を辿ろうとした場合、１度A-B間の辺を伝ってBに渡り、また別のA-B間の辺を伝ってAに戻らなければならない。
K<=7なので、この行き来は１往復しかない。

AとBの辺の張り方をnext_permutationでN!通り作成する。
そして、Aから２点Ai,Ajを選んだとき、それぞれからつながるBの２点をBk,Blとして、dist(Ai,Aj)+dist(Bk,Bl)+2==Kなら長さKの閉路が１本できる。

計算量はO(N!*N^2)でNの指数関数になるが、N<=9なので十分間に合う。
再帰にFloyd法で点の間の距離を計算しておくとラク。

class TreeUnionDiv2 {
	int T,K;
	int dist[2][10][10];
	vector<int> P;
	public:
	
	int maximumCycles(vector <string> tree1, vector <string> tree2, int K) {
		int i,j,k,x,y,z;
		T=tree1.size();
		this->K=K;
		FOR(x,T) FOR(y,T) dist[0][x][y]=(tree1[x][y]=='X')?1:100;
		FOR(x,T) FOR(y,T) dist[1][x][y]=(tree2[x][y]=='X')?1:100;
		FOR(x,T) dist[0][x][x]=dist[1][x][x]=0;
		FOR(i,T) FOR(j,T) FOR(k,T) dist[0][j][k] = min(dist[0][j][k], dist[0][j][i]+dist[0][i][k]);
		FOR(i,T) FOR(j,T) FOR(k,T) dist[1][j][k] = min(dist[1][j][k], dist[1][j][i]+dist[1][i][k]);
		P.clear();
		FOR(i,T) P.push_back(i);
		
		int ma=0;
		do{
			//select2
			int res=0;
			FOR(x,T) for(y=x+1;y<T;y++) {
				if(2+dist[0][x][y]+dist[1][P[x]][P[y]]==K) res++;
			}
			ma=max(ma,res);
		}while(next_permutation(P.begin(),P.end()));
		
		return ma;
	}
};

まとめ

これはさっくり解けて良かった。