E. Museums Tour
分析：
按时间建出分层图，每个点形如(u,t)，表示u在在t个时刻的点，tarjan缩点。每个强连通分量中的点都能经过，然后DAG上dp。
代码：
#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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; } const int N = 5000005; 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[100001][51]; void tarjan(int u) { dfn[u] = low[u] = ++TimeIndex; sk[++top] = u; vis[u] = 1; 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]] = 0; bel[sk[top]] = SCC; top--; } while (sk[top + 1] != u); } } int dfs(int u) { // DAG上dp if (dp[u]) return dp[u]; int ans = 0; 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 = 1; i <= m; ++i) { int u = read(), v = read(); for (int j = 0; j < d; ++j) G1.add_edge(getid(u, j), getid(v, (j + 1) % d)); } for (int i = 1; i <= n; ++i) scanf("%s", s[i]); for (int i = 1; i <= tot; ++i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++i) { for (int j = 0; j < d; ++j) { int x = getid(i, j); if (s[i][j] == '1' && 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[1]); return 0; }