Typical DP Contest R - グラフ

問題

N頂点からなる有向グラフが与えられる。
最初全ての頂点は白で、グラフにパス（同じ頂点を何度通ってもよい）を描くと、
パス上の頂点の色が全て黒になる。
この操作を２回できるとき、黒にできる頂点の個数の最大値を求めよ。

制約条件

N≦300

方針

まずは強連結成分分解してDAGに。
トポロジカルソートをして、DAGの根元のほうからDPする。

２本のパスの先端の部分を持つようなDP.
それぞれi, jとすると、iを伸ばすかjを伸ばすか。
以下iを伸ばす場合を考える。

iを伸ばした先kが、jの先祖である場合、jがkを既に通っている可能性がある。
したがって、そのような遷移を不可能にしてやる。

iを伸ばした先kがjの先祖でなければ、普通にパスを伸ばしてよい。
iを伸ばした先kが、jの先祖である場合は、iがjを飛び越すまでスキップして、jの先にkを出してやるようにすれば、全ての場合が尽くされる。

トポロジカル順にDPするのがちゃんとできてなくてちょっとはまった。

ソースコード

int n, sz[300];
bool e[300][300], g[300][300];
vi ord;
 
int dp[300][300];
 
void pre(){
	int m;
	bool ee[300][300];
	cin >> m;
	
	Graph gg(m);
	rep(i, m) rep(j, m){
		cin >> ee[i][j];
		if(ee[i][j]) gg[i].pb(Edge(i, j, 0));
	}
	
	int to[300];
	vector<vi> scc;
	stronglyConnectedComponents(gg, scc);
	
	rep(i, scc.size()){
		rep(j, scc[i].size()) to[scc[i][j]] = i;
		sz[i] = scc[i].size();
	}
	
	n = scc.size();
	Graph g2(n);
	
	rep(i, m) rep(j, m) if(ee[i][j]){
		
		int a = to[i], b = to[j];
		if(a != b && !e[a][b]){
			g[a][b] = e[a][b] = 1;
			g2[a].pb(Edge(a, b, 0));
		}
	}
	topologicalSort(g2, ord);
	
	rep(i, n) g[i][i] = 1;
	rep(k, n) rep(i, n) rep(j, n) g[i][j] |= g[i][k] && g[k][j];
}
int main(){
	pre();
	
	rep(i, n) for(int j = i; j < n; j++){
		dp[i][j] = max(dp[i][j], sz[ord[i]] + (i != j ? sz[ord[j]] : 0));
		
		rep(k, n) if(i != k && j != k){
			if(!g[ord[k]][ord[j]] && e[ord[i]][ord[k]] ||
				g[ord[i]][ord[j]] && e[ord[j]][ord[k]]){
					
					int l = min(k, j), r = max(k, j);
					dp[l][r] = max(dp[l][r], dp[i][j] + sz[ord[k]]);
			}
			if(!g[ord[k]][ord[i]] && e[ord[j]][ord[k]] ||
				g[ord[j]][ord[i]] && e[ord[i]][ord[k]]){
					
					int l = min(k, i), r = max(k, i);
					dp[l][r] = max(dp[l][r], dp[i][j] + sz[ord[k]]);
			}
		}
	}
	
	int ans = 0;
	rep(i, n) rep(j, n) ans = max(ans, dp[i][j]);
	cout << ans << endl;
	
	return 0;
}