[CF1137C] Museums Tour 题解
首先看到 \(d\le 50\)，考虑拆点。
把一个点拆成 \(d\) 个点，分别代表到这个点的时候是周几。
然后对于一条有向边，每一天向出边的下一天连边。
这样观察发现，如果两个点在同一个强连通分量内，那么它们可以无限转圈，也就是说，只要到达了一个 SCC 内的点，SCC 内其它的点都可以到达。
所以 SCC 内点的性质差不多，直接缩点，缩点之后给每个 SCC 赋权，点权设为这个 SCC 内部有多少天开放博物馆。
所以如果同一个博物馆不同天都在同一个 SCC 内 或者互相不可达，那么答案就是从 1 开始的最长链。
可以证明，不会存在同一个博物馆不同天数不在同一个 SCC 内并且一个点可以到另一个点。
假设存在 \((i, j)\) 可以通过 \(x\) 天到达 \((i, k)\)，且不在一个 SCC 内，那么根据这张图的对称性， \((i, k)\) 可以经过 \(x\) 天到达 \((i, (k - j + k)\bmod d)\)。
所以可以草率的列出同余等式：\[j+x\equiv k\pmod d\\ j\equiv k -x\pmod d\\ k - x + dx\equiv j \pmod d\\ k+(d-1)x\equiv j\pmod d \]所以在走 \(d - 1\) 次上述道路就可以回到 \((i, j)\)，所以 \((i, j), (i, k)\) 强连通，矛盾假设不成立原命题得证。
所以直接缩点跑最长链即可。
这题卡空间，用链式前向星好一点，另外爆栈可以换编译器试试，时间复杂度：\(O(d(n + m))\)。
// Problem: Museums Tour
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-10-15 19:54:05
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
// #define int long long
using namespace std;
const int N = 5e6 + 1, M = N;
int n, m, d;
int h[N], ne[M], e[M], idx, h2[N], ne2[M], e2[M], idx2;
inline void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
inline void add2(int a, int b) {
e2[idx2] = b, ne2[idx2] = h2[a], h2[a] = idx2++;
}
int dfn[N], y, low[N], timestamp, stk[N], top, id[N], scc, sz[N], dp[N];
bool ins[N], w[N];
int s[N], tot;
inline void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp, stk[++ top] = u, ins[u] = 1;
for(int i = h[u], v; ~i; i = ne[i]) {
v = e[i];
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
y; scc ++;
tot = 0;
while(y != u) {
y = stk[top --], id[y] = scc, ins[y] = 0;
if(w[y]) s[++ tot] = y % n;
}
sort(s + 1, s + tot + 1);
sz[scc] = unique(s + 1, s + tot + 1) - s - 1;
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> d;
memset(h, -1, sizeof h), memset(h2, -1, sizeof h2);
for(int i = 1, a, b; i <= m; i ++) {
cin >> a >> b;
for(int j = 0; j < d; j ++)
add(a + j * n, b + (j + 1) % d * n);
}
char c;
for(int i = 1; i <= n; i ++) {
for(int j = 0; j < d; j ++) {
cin >> c;
if(c == '1') w[i + n * j] = 1;
}
}
for(int i = 1; i <= d * n; i ++) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= d * n; i ++) {
for(int k = h[i], j; ~k; k = ne[k]) {
j = e[k];
if(id[i] != id[j])
add2(id[i], id[j]);
}
}
memset(dp, -0x3f, sizeof dp);
dp[id[1]] = sz[id[1]];
int ans = 0;
for(int i = scc; i; i --) {
for(int j = h2[i], k; ~j; j = ne2[j]) {
k = e2[j];
dp[k] = max(dp[i] + sz[k], dp[k]);
}
ans = max(ans, dp[i]);
}
cout << ans << '\n';
return 0;
}