TopCoder SRM 608 Div1 Medium BigO

さっきのDiv2 Hardを解いておくとかなり楽。
http://community.topcoder.com/stat?c=problem_statement&pm=13001

問題

さっきのDiv2 Hardと類似している。
有向グラフに対し、非常に大きな長さLのパスをたどることを考える。
この時、長さLのパスの組み合わせ数の上限がLの多項式で表せ、O(L^K)となるならそのKを答えよ。
多項式より大きいなら-1と答えよ。

解法

まず、多項式を超えるケースはさっきのDiv2 Hardの通り、１周で２通り以上の閉路がある場合である。

では多項式となるのはどういう場合か。
これはいくつかの閉路があって、それらが戻れないパスでつながっている場合である。

例えば以下の場合を考える。○を１つの閉路と見る。
○→○→○→○
このグラフでは、個々の閉路から次の閉路に移るタイミングが３回とれる。
Lが長くなればなるほど、それぞれの遷移のタイミングも長い間から選択できるので、O(L^3)とみなせる。

この事実より、以下の解法で良いことがわかる。

• まずグラフを強連結成分分解する
• 強連結成分分解した個々の要素間が遷移可能であればそのコストを１とし、最長パスを求めるとそれが答え。

以下のコードでは強連結成分分解はWF法で閉路を求めてUnion-find法で求めた。
最長パスは念のためN^4のループを回しているけど、WF法の要領でN^3で求めてもいいのかな。

int dist[51][51];
int dist2[51][51];

const int ufmax=1001;
int ufpar[ufmax],ufrank[ufmax];
void UF_init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
int UF_find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = UF_find(ufpar[x]));}
void UF_unite(int x,int y) {
	x = UF_find(x); y = UF_find(y);
	if(x==y) return;
	if(ufrank[x]<ufrank[y]) ufpar[x]=y;
	else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
}

class BigO {
	int N;
	int vis[51];
	int nloop[51];
	vector<string> G;
	public:
	
	int minK(vector <string> graph) {
		G=graph;
		N=graph.size();
		
		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];
		
		UF_init();
		FOR(i,N) {
			nloop[i]=0;
			FOR(x,N) if(i!=x && G[i][x]=='Y' && dist[x][i]) nloop[i]++,UF_unite(i,x);
			if(nloop[i]>1) return -1;
		}
		
		if(count(nloop,nloop+N,1)==0) return 0;
		
		ZERO(dist2);
		
		FOR(x,N) FOR(y,N) if(nloop[x]==1 && nloop[y]==1 && dist[x][y] && UF_find(x) != UF_find(y)) dist2[UF_find(x)][UF_find(y)]=1;
		int ma=0;
		FOR(i,N) FOR(x,N) FOR(y,N) FOR(z,N) {
			if(x!=z && z!=y && x!=y && dist2[x][z] && dist2[z][y]) dist2[x][y]=dist2[x][z]+dist2[z][y];
			ma=max(ma,dist2[x][y]);
		}
		
		return ma;
	}
};

まとめ

実装は若干重いけど、問題形式が面白かった。