yukicoder : No.19 ステージの選択

☆４つだけど、SRM Div1Mediumとかよりは楽。
http://yukicoder.me/problems/62

問題

N個のステージからなるゲームがある。
各ステージをクリアするコストはL[i]である。
ただし、各ステージにおいて、先にステージS[i]をクリアしていると、クリアコストは半分のL[i]/2になる。
(S[i]は各ステージに１個ずつしかない)

最適な順でステージをクリアしたとき、総コストの最小値を答えよ。

解法

基本的にはトポロジカルソートで、すでにクリアコストが半減化したステージから順次クリアしていけば良い。
ただし、先にクリアしたいステージ群が循環しているとトポロジカルソートできない。
この場合、循環したステージ群において、コストが半減するメリットが最小である元々最小コストのステージを最初にクリアすればよい。

int N;
int L[101],S[101];
int vis[101],done[101];

int dfs(int cur,int tar) {
	int x;
	if(done[S[cur]]) return -1;
	if(cur==tar) return tar;
	if(vis[S[cur]]) return -1;
	
	vis[cur]=1;
	x = dfs(S[cur],tar);
	
	if(x<0) return -1;
	if(L[cur]<L[x]) return cur;
	return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i]>>S[i], L[i]*=2, S[i]--;
	
	int ret=0;
	FOR(i,N) if(done[i]==0) {
		ZERO(vis);
		x=dfs(S[i],i);
		if(x>=0) ret += L[x], done[x]=1;
	}
	FOR(i,N) FOR(j,N) if(done[S[j]] && done[j]==0) done[j]=1, ret+=L[j]/2;
	
	_P("%.1lf\n",ret*0.5);
}

まとめ

タグに強連結成分分解とあってびっくりするけど、各頂点の出次数は１しかないので強連結成分と言っても単純なループのみ。