AtCoder ARC #030 : C - 有向グラフ

いつもより若干Cが難しめ？
http://arc030.contest.atcoder.jp/tasks/arc030_3

問題

N頂点M辺の有向グラフが与えられる。
各頂点にはアルファベットが１文字ずつ置いてある。

ここで、任意の頂点からスタートし、任意回数有向辺をたどることを考える。
その際、経由した頂点に置かれた文字を回収しても良いししなくても良い。
２回目以降に各頂点に到達した際に回収しても良いが、１度回収した頂点からは２度は回収できない。

アルファベットを回収順に並べてできる文字列のうち、K文字で辞書順最小のものを答えよ。

解法

閉路ができている場合、閉路内のアルファベットは任意順で回収できるので、辞書順に小さい順に回収すればよい。

この考えをもとに、まずは全体を強連結成分分解する。
なおこの際、任意の頂点からスタートするケースを考えるのは面倒なため、ダミー頂点を作り、そこから各頂点に有向辺を追加しておく。
こうするとダミー頂点を常に始点とすることができる。

強連結成分を求め、かつそれらをトポロジカルソートしたら、有向辺の逆順に
「各成分およびそれ以降の連結成分を用いて生成できる辞書順最小のL文字の文字列」を各Lに対して実行し、DPしていけばよい。
その際、連結成分内の文字を使う場合は事前にソートしておき、頭から順に使うと良い。

class SCC {
public:
	static const int MV = 5000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

int N,M,K;
char C[500];

string S[501];
SCC scc;
set<int> E[502], E2[502];
int out[502];
string SS[302][302];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	C[0]='a';
	FOR(i,N) cin>>s, C[i+1]=s[0];
	N++; K++;
	
	scc.init(N);
	FOR(x,N-1) scc.add_edge(0,x+1), E[0].insert(x+1);
	FOR(i,M) cin>>x>>y, scc.add_edge(x,y), E[x].insert(y);
	
	scc.scc();
	FOR(x,N) ITR(it,E[x]) if(scc.GR[x]!=scc.GR[*it]) E2[scc.GR[x]].insert(scc.GR[*it]);
	
	for(i=scc.SC.size()-1;i>=0;i--) {
		FOR(j,scc.SC[i].size()) S[i]+=C[scc.SC[i][j]];
		sort(S[i].begin(),S[i].end());
		
		FOR(j,S[i].size()+1) SS[i][j]=S[i].substr(0,j);
		for(x=S[i].size(); x>=0; x--) {
			ITR(it,E2[i]) {
				for(y=1;SS[*it][y].size(); y++) {
					if(SS[i][x+y].size()==0 || SS[i][x+y]>SS[i][x]+SS[*it][y]) SS[i][x+y] = SS[i][x]+SS[*it][y];
				}
			}
		}
	}
	
	if(SS[scc.GR[0]][K].size()<K) cout << -1 << endl;
	else cout << SS[scc.GR[0]][K].substr(1) << endl;
}

まとめ

本番「強連結成分分解すればいいのかなー」と思いつつ、「Cで強連結成分分解＋DPなんて出るかな？」とDを見に行ったりしてタイムロスしてしまった。