立命館合宿2013 3日目 E Twins Idol

制約条件

n≦100
m≦5000

方針

まずは強連結成分分解する。
Gの大きさ2以上の強連結成分に含まれる文字と、
G'の大きさ2以上の強連結成分に含まれる文字に共通のものがあったら、
無限に得点が得られてしまうので-1を出力する。


強連結成分分解をしたら、G, G'はDAGになるので、
メモ化再帰でDPする。


遷移がやや複雑。
大きさが1の強連結成分で得点を得た場合は、必ず次の強連結成分に行く。
大きさが2以上の強連結成分で得点を得た場合は、その連結成分にいくらでもとどまれる。

ソースコード

かなり実装ミスった。半分くらいの行数で書けるはず。

int n, m, N, M;
char c[100], C[100];
vector<vi> e, E, g, G;
vector<vi> scc, SCC;

int dp[110][110];
int rec(int a, int b){
	int &res = dp[a][b];
	if(res >= 0) return res;
	
	int gain = 0, x[256] = {}, y[256] = {};
	rep(i, scc[a].size()) x[c[scc[a][i]]]++;
	rep(i, SCC[b].size()) y[C[SCC[b][i]]]++;
	rep(i, 256) gain += min(x[i], y[i]);
	
	res = gain;
	rep(i, g[a].size()) res = max(res, rec(g[a][i], b) + (SCC[b].size() > 1 ? gain : 0));
	rep(i, G[b].size()) res = max(res, rec(a, G[b][i]) + (scc[a].size() > 1 ? gain : 0));
	
	rep(i, g[a].size()) rep(j, G[b].size())
	res = max(res, rec(g[a][i], G[b][j]) + gain);
	
	return res;
}

int main(){
	cin >> n >> m;
	e.resize(n);
	rep(i, n) cin >> c[i];
	rep(i, m){
		int a, b;
		cin >> a >> b;
		e[a - 1].pb(b - 1);
	}
	cin >> N >> M;
	E.resize(N);
	rep(i, N) cin >> C[i];
	rep(i, M){
		int a, b;
		cin >> a >> b;
		E[a - 1].pb(b - 1);
	}
	
	stronglyConnectedComponents(e, scc);
	stronglyConnectedComponents(E, SCC);
	
	map<int, int> to, TO;
	rep(i, scc.size()) each(j, scc[i]) to[*j] = i;
	rep(i, SCC.size()) each(j, SCC[i]) TO[*j] = i;
	
	bool can[256] = {};
	rep(i, scc.size()) if(scc[i].size() > 1) rep(j, scc[i].size()){
		can[c[scc[i][j]]] = 1;
	}
	rep(i, SCC.size()) if(SCC[i].size() > 1) rep(j, SCC[i].size()){
		if(can[C[SCC[i][j]]]){
			cout << -1 << endl;
			return 0;
		}
	}
	
	int in[100] = {}, IN[100] = {};
	g.resize(scc.size());
	G.resize(SCC.size());
	rep(i, e.size()) rep(j, e[i].size()){
		int a = to[i], b = to[e[i][j]];
		if(a != b) g[a].pb(b), in[b]++;
	}
	rep(i, E.size()) rep(j, E[i].size()){
		int a = TO[i], b = TO[E[i][j]];
		if(a != b) G[a].pb(b), IN[b]++;
	}
	
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	rep(i, g.size()) if(in[i] == 0) rep(j, G.size()) if(IN[j] == 0)
	ans = max(ans, rec(i, j));
	
	cout << ans << endl;
	
	return 0;
}