TopCoder SRM 608 Div1 Medium BigO

問題

n頂点からなる有向グラフが与えられる。
整数Lに対して、このグラフ上の長さLのウォークの個数がO(L^k)で抑えられるような最小のkを求めよ。

そのようなLが存在しないとき、は-1を返せ。

制約条件

n≦50
長さlのウォークとは、グラフの頂点の列v1, v2, ..., vlで、viとvi+1の間に辺があるようなものをいう。同じ頂点および辺を何度使ってもよい。
Lについての関数がO(L^k)であるとは任意のLに対してその関数が定数Cを使って
f(L) ≦ C * L^kと抑えられることを言う。

方針

-1にならないグラフというのは、相当強い制約がかかりそうというのがサンプルを見るとわかる。
よく考えてみると、頂点iから出発して、iに戻ってくる方法が２通り以上あると、ウォークの個数はO(L^k)で抑えられないことがわかる。
なので、まずは自分に２通り以上の方法で戻れないかをみてやればよい。

戻れない場合、ループがDAGのようにつながったグラフになる。
ループを一個下る度に、場合の数のオーダーが一次増える（Lのうち何歩目で下のループに移るか選べるから）

違うループに行く方法が２通り以上あっても定数倍なので、オーダーには関係ない。

以上のことから、強連結成分分解したグラフを考えて、一番長いチェーンの長さが答え。
実装はなんか適当に色々手を抜いている。

ソースコード

int n, way[100][50][50]; //i歩でjからkへ行く場合の数
bool can[50][50]; //iからjへ到達可能か
int dp[50];

int rec(int c){
	int &res = dp[c];
	if(res >= 0) return res;
	res = 0;
	//自分より下のループの最大値 + 1が答え
	rep(i, n) if(can[c][i] && !can[i][c] && can[i][i]) res = max(res, rec(i) + 1);
	return res;
}
class BigO {
	public:
	int minK(vector <string> graph) {
		memset(way, 0, sizeof(way));
		memset(dp, -1, sizeof(dp));
		
		n = graph.size();
		rep(i, n) rep(j, n) can[i][j] = way[1][i][j] = graph[i][j] == 'Y';
		rep(i, n) way[0][i][i] = 1;
		
		for(int it = 1; it < 99; it++) rep(k, n) rep(i, n) rep(j, n){
			int &w = way[it + 1][i][j];
			w += way[it][i][k] * way[1][k][j];
			w = min(w, 2); //1より大きいのは全部同じなので2で打ち切り
		}
		rep(i, n){
			int t = -1;
			for(int j = 1; j < 100; j++) if(way[j][i][i]){
				t = j;
				break;
			}
			if(t < 0) continue;
			for(int j = 1; j < 100; j++) if(way[j][i][i] != (j % t == 0 ? 1 : 0)) return -1;
		}
		
		rep(k, n) rep(i, n) rep(j, n) can[i][j] |= can[i][k] && can[k][j];
		int ans = 0;
		rep(i, n) if(can[i][i]) ans = max(ans, rec(i));
		
		return ans;
	}
};