立命館合宿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; }