CF 1138 E. Museums Tour

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#define getid(a, b) ((a - 1) * d + b + 1)
using namespace std;
typedef long long LL;inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
}const int N = ;
struct Graph {
int head[N], nxt[N], to[N], En;
inline void add_edge(int u,int v) {
++En; to[En] = v, nxt[En] = head[u]; head[u] = En;
}
}G1, G2;
int dfn[N], low[N], sk[N], bel[N], vis[N], siz[N], dp[N], TimeIndex, SCC, top;
char s[][];void tarjan(int u) {
dfn[u] = low[u] = ++TimeIndex; sk[++top] = u; vis[u] = ;
for (int i = G1.head[u]; i; i = G1.nxt[i]) {
int v = G1.to[i];
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++SCC;
do { vis[sk[top]] = ; bel[sk[top]] = SCC; top--; } while (sk[top + ] != u);
}
}
int dfs(int u) { // DAG上dp
if (dp[u]) return dp[u];
int ans = ;
for (int i = G2.head[u]; i; i = G2.nxt[i])
ans = max(ans, dfs(G2.to[i]));
dp[u] = siz[u] + ans;
return dp[u];
}
int main() {
int n = read(), m = read(), d = read(), tot = n * d;
for (int i = ; i <= m; ++i) {
int u = read(), v = read();
for (int j = ; j < d; ++j)
G1.add_edge(getid(u, j), getid(v, (j + ) % d));
}
for (int i = ; i <= n; ++i) scanf("%s", s[i]);
for (int i = ; i <= tot; ++i) if (!dfn[i]) tarjan(i);
for (int i = ; i <= n; ++i) {
for (int j = ; j < d; ++j) {
int x = getid(i, j);
if (s[i][j] == '' && vis[bel[x]] != i) vis[bel[x]] = i, siz[bel[x]] ++; // 每个点在一个强连通分量中只能计算一次
for (int k = G1.head[x]; k; k = G1.nxt[k])
if (bel[x] != bel[G1.to[k]]) G2.add_edge(bel[x], bel[G1.to[k]]);
}
}
cout << dfs(bel[]);
return ;
}