TopCoder SRM 530 Div2 Hard GogoXReimuHakurai

問題

n個のステージがあるゲームをする。
最初ステージ0からスタートして、n-1にたどり着いたらクリアである。

ステージiをクリアした後ステージjに移動できるかどうかの関係がグラフにより与えられる。

ゲームクリアを、「今までのクリアで一回も使われていない道がひとつ以上あるようなルート」で、できるだけ行う。
ゲームは何回クリアできるか、求めよ。

制約条件

n≦50
iからjに辺があるとき、i＜j

方針

次のようなことを繰り返したら通った。

• visitedのノードを、最初0とn-1とする。
• 更新がなくなるまで以下を繰り返す
• visitedなノードi,jについて、iからjに未使用な辺だけからなるパスがあるなら答えに+1
• iからjへのパス上の辺を全て使用済みにする。iからjへのパス上にあった頂点をvisitedに加える。

何故これで通ったのかはよくわからない。

ソースコード

bool can[50][50];

class GogoXReimuHakurai {
	public:
	int solve(vector <string> choices) 
	{
		int n=choices.size();
		bool v[50]={};
		v[0]=v[n-1]=1;
		
		int ans=0;
		for(;;){
			bool update=0;
			rep(i,n)rep(j,n)can[i][j]=choices[i][j]=='Y';
			rep(k,n)rep(i,n)rep(j,n)can[i][j]|=can[i][k]&&can[k][j];
			
			rep(i,n)rep(j,n)if(v[i]&&v[j]&&can[i][j]){
				queue<int> q;
				int prev[50];
				rep(k,n)prev[k]=-1;
				q.push(i);
				while(!q.empty()){
					int c=q.front(); q.pop();
					rep(k,n)if(choices[c][k]=='Y'&&prev[k]<0)q.push(k), prev[k]=c;
				}
				for(int c=j;prev[c]>=0;c=prev[c]){
					choices[prev[c]][c]='N';
					v[prev[c]]=v[c]=1;
				}
				update=1;
				ans++;
				goto NEXT;
			}
			NEXT:;
			if(!update)break;
		}
		return ans;
	}
};