【CF1137C】Museums Tour 题解

题目大意

  有一幅 $n$ 个点 $m$ 条边的有向图，每个点有一个博物馆，一周有 $d$ 天。每个博物馆在每一天的开闭状态是已知的（一个大的 01 矩阵）。
  一开始你在 $1$ 号点星期 $1$，每天如果当前所在的博物馆开馆，你就可以去访问它，当这一天结束时，你必须向前走一步或者结束行程。
  求你最多能访问多少个不同的博物馆。

  $n,m \leq 10^5,\ d\leq50$

$$\\$$ $$\\$$ $$\\$$

题解

  首先想到要拆点，一个点拆成 $d$ 个，表示这个点星期几。然后现在就变成了一幅 $nd$ 个点 $md$ 条边的有向图。

  一个强连通分量内部是互相可达的，于是想到缩起来变成一幅 DAG。

  那现在有了这个 DAG 之后干啥呢？

  一开始肯定想 dp 啊，设 $f_i$ 表示从第 $i$ 个强连通分量开始最多能访问多少博物馆。然后从它连出去的所有点里面找个最大的转移过来。

  但是这样就会想到一个问题啊，后面的强连通分量包含了第 $i$ 个点星期 $j$，而现在的强连通分量包含第 $i$ 个点星期 $j’$，这不就计重了吗？甚至前面的强连通分量还会包含第 $i$ 个点星期 $j’’$ 呢！

  于是傻逼如我就开始想用 set 来代替个数，这样就不会计重了。然后这样 dp 就成了启发式合并 set。
  但是这样依然有问题啊，第 $i$ 个点你得跟儿子合并了取 size 才知道这样转移的好坏，那合并 set 就还得撤销了啊！！而且这样转移，是有后效性的。
  然后我就崩了。

  因此要想题解那样发现一个很强的性质——不存在计重的情况！！
  设 $i$ 号点星期 $x$ 可以走到 $i$ 号点星期 $y$，即存在路径 $(i,x) \to (i,y)$。设 $\Delta d=y-x$，那么这条路径还可以继续扩展： $(i,x) \to (i,y) \to (i,y+\Delta d) \to (i,y+2\Delta d) \to … \to (i,y+(d-1)\Delta d)$，这个就是 $(i,x)$ 了，也就是说 $(i,y)$ 也是能走回到 $(i,x)$ 的！
  也就是说，一个点拆出来的几个状态，如果能从一个到达另一个，那它们一定是在同一个强连通分量里的。
  这样 dp 就没有顾虑了，就直接 dp 了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1e5+5, maxd=55, maxN=5e6+5, maxe=5e6+5;

int n,m,d,num[maxN];

int getid(int i,int j) {return i+n*(j-1);}

int tot,go[maxe],nxt[maxe],f1[maxN];
void ins(int x,int y)
{
	go[++tot]=y;
	nxt[tot]=f1[x];
	f1[x]=tot;
}
int tot2,go2[maxe],nxt2[maxe],f2[maxN],com[maxN];
void ins2(int x,int y)
{
	go2[++tot2]=y;
	nxt2[tot2]=f2[x];
	f2[x]=tot2;
	com[y]++;
}

int sum,dfn[maxN],low[maxN],bz[maxN],z0,z[maxN],rt[maxN];
void tarjan(int k)
{
	dfn[k]=low[k]=++sum;
	bz[k]=1;
	z[++z0]=k;
	for(int p=f1[k]; p; p=nxt[p])
	{
		if (!bz[go[p]])
		{
			tarjan(go[p]);
			low[k]=min(low[k],low[go[p]]);
		} else if (bz[go[p]]==1) low[k]=min(low[k],dfn[go[p]]);
	}
	if (dfn[k]==low[k])
	{
		do{
			bz[z[z0]]=2;
			rt[z[z0]]=k;
		} while (z[z0--]!=k);
	}
}

int f[maxN],q[maxN];
void topo()
{
	int j=0;
	fo(i,1,n*d) if (rt[i]==i && !com[i]) q[++j]=i;
	for(int i=1; i<=j; i++)
	{
		f[q[i]]+=num[q[i]];
		for(int p=f2[q[i]]; p; p=nxt2[p])
		{
			f[go2[p]]=max(f[go2[p]],f[q[i]]);
			if (--com[go2[p]]==0) q[++j]=go2[p];
		}
	}
}

char s[maxd];
int main()
{
	scanf("%d %d %d",&n,&m,&d);
	fo(i,1,m)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		fo(j,1,d) ins(getid(x,j),getid(y,j%d+1));
	}
	
	tarjan(1);
	memset(bz,0,sizeof(bz));
	fo(i,1,n)
	{
		scanf("%s",s+1);
		fo(j,1,d) if (s[j]=='1')
		{
			int id=rt[getid(i,j)];
			if (!bz[id]) bz[id]=1, num[id]++;
		}
		fo(j,1,d) bz[rt[getid(i,j)]]=0;
	}
	fo(i,1,n*d)
		for(int p=f1[i]; p; p=nxt[p]) if (rt[go[p]]!=rt[i] && rt[go[p]] && rt[i])
			ins2(rt[go[p]],rt[i]);
	topo();
	
	printf("%d\n",f[1]);
}