CF1137C 【Museums Tour】
Rainbow_qwq
2020-06-01 16:33:02
[CF1137C Museums Tour
](https://www.luogu.com.cn/problem/CF1137C)
---
# 思路
分层图 & 强连通缩点。
注意一些要点：
1. 只要能走，旅行者可以走无数天。
2. 一周 $d$ 天的开放是循环的。
于是我们可以想到拆点，把一个点 $u$ 拆成 $[u,0],[u,1],\dots,[u,d-1]$，这样每个点的博物馆对应一个确定的状态 开/关。
对于原图上的边 $u\to v$ ，拆成 $d$ 条边 $[u,i]\to [v,(i+1)\bmod d] (0\le i\le d-1)$ ，相当于今天的 $u$ 向明天的 $v$ 连边。
然后从 $[1,0]$ 开始跑一次最长路就可以了？不行，图上还有环。
于是想到 Tarjan 缩点，每个强连通分量的点权为 **这个强连通分量中开启的不同博物馆个数**。
缩点后形成一个 DAG 就可以直接 dfs 求最长路了。
Q: 会不会重复统计相同博物馆？
不会的，假设 $[u,i]$ 与 $[u,j]$ 在不同强连通分量且 $[u,i]$ 可到 $[u,j]$ ，那么从 $[u,j]$ 也能走到 $[u,i]$ 。
upd:上面那句话的证明如下：
如果存在 $[i,a]\to [i,a+x]$ ，那么
$[i,a+x]\to[i,a+x+x]$ ， 以此类推 $[i,a+x]\to [i,(a+x*d)\ \bmod \ d]$
而 $[i,(a+x*d)\ \bmod \ d]$ 就是 $[i,a]$
也就是说 如果 $[i,a]\to [i,a+x]$ ，那么
$[i,a+x]\to[i,a]$
时间/空间复杂度 $O(nd)$ 。
这题思路还是挺顺的（
# 代码
有点难写，还要注意不被卡空间（
注意：计算点权的时候，vis 数组不能 memset 。
```cpp
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define maxn 100005
#define N 100005*50
int n,m,k;
long long sta[maxn];
struct edge{
int to,nxt;
}e[N],e2[N];
int tot,tot2,head[N],head2[N];
inline void adde(int u,int v){
e[++tot]=(edge){v,head[u]};
head[u]=tot;
}
inline void adde2(int u,int v){
e2[++tot2]=(edge){v,head2[u]};
head2[u]=tot2;
}
int idx,scc,bel[N],dfn[N],low[N];
int f[N],val[N];
bool ins[N],vis[N];
stack<int>s,q;
inline void tarjan(int u){
dfn[u]=low[u]=++idx;
ins[u]=1;s.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
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])return;
++scc;int v;
do{
v=s.top();s.pop();
ins[v]=0,bel[v]=scc;
int x=(v-1)%n+1,day=(v-1)/n;
// x:哪个城市
// day:哪天
if(!vis[x] && (sta[x]>>day&1)){
val[scc]++,vis[x]=1;
q.push(x);
}
}while(u!=v);
while(!q.empty())vis[q.top()]=0,q.pop();
}
inline int P(int i,int j){
return j*n+i;
}
//dfs 最长路
int dfs(int u)
{
if(vis[u])return f[u];
vis[u]=1;
for(int i=head2[u];i;i=e2[i].nxt){
int v=e2[i].to;
f[u]=max(f[u],dfs(v));
}
return f[u]+=val[u];
}
int main()
{
n=read(),m=read(),k=read();
For(i,1,m){
int u=read(),v=read();
For(j,0,k-1)adde(P(u,j),P(v,(j+1)%k));
}
char ch;
For(i,1,n)
For(j,0,k-1){
while(!isdigit(ch=getchar()));
sta[i]|=1ll*(ch-'0')<<j;
}
tarjan(1);
For(i,1,n*k)
{
if(!dfn[i])continue;
int u=bel[i];
for(int j=head[i];j;j=e[j].nxt){
int v=e[j].to;
if(!dfn[v])continue;
v=bel[v];
if(u!=v)adde2(u,v);
}
}
cout<<dfs(bel[1]);
return 0;
}
```