TopCoder SRM 608 Div2 Hard BigOEasy

こちらを解いておくと、Div1 Mediumがだいぶとっつきやすくなる。
http://community.topcoder.com/stat?c=problem_statement&pm=13002

問題

有向グラフが与えられる。
このグラフに対して、長さLのパスの組みわせ数を考える。
非常に大きなLに対し、組み合わせ数の上限がLの対する多項式に収まるかどうかを答えよ。

解法

まず前提として、閉路がないと大きなLに対してパス数が0になるので、閉路がない場合は多項式に収まる。
ある点から元の点に戻る閉路に対し、１周たどるのに２つ以上のパスがある場合、１周ごとに選択肢が倍になるので組み合わせ数はO(2^L)とLの指数関数になるため、多項式に収まらない。

よって、２つ以上のパスがある閉路があるか求めればよい。
以下の処理ではワーシャルフロイト法でまず閉路の有無を求めたうち、各点から１手目を異なる点に移動したとき、元の点に戻れる点の数をカウントすることで閉路の数を求めている。

すなわち：

• 異なる初手から元の点に戻れる点が２個以上あるような点が１個でもあれば多項式に収まらない。
• その反対、すなわち閉路がないか、あっても各点の初手が１点のみの場合、多項式に収まる。

class BigOEasy {
	public:
	
	string isBounded(vector <string> graph) {
		vector<string> G=graph;
		int N=graph.size();
		int dist[51][51];
		
		int i,x,y,z;
		FOR(x,N) FOR(y,N) dist[x][y]=(G[x][y]=='Y');
		FOR(i,N) FOR(x,N) FOR(y,N) dist[x][y] |= dist[x][i]&&dist[i][y];
		
		FOR(x,N) {
			int r=0;
			FOR(y,N) if(y!=x && G[x][y]=='Y' && dist[y][x]) r++;
			if(r>1) return "Unbounded";
		}
		return "Bounded";
	}
};

まとめ

最初は閉路をDFSで求めたけど、50点位ならWF法で十分だね。
おかげでコードはかなり短くなった。