P6698-[BalticOI 2020 Day2]病毒【AC自动机,dp,SPFA】

正题

题目链接:https://www.luogu.com.cn/problem/P6698

---

题目大意

有一个包含$0\sim G-1$的字符集，其中有$n$种变换，能够将一个字符$a_i(a_i>1)$变为一串字符$b_i$，当一个字符串中只剩下$0$和$1$时变换就结束了。

然后给出$m$个匹配串$c_i$。现在对于每个字符$i\in [2,G-1]$，是否字符$i$无论变化结束时都含有至少一个匹配串，如果不是，求一个最短的不包含任何匹配串的最终串长度。

保证每个在$[2,G-1]$的字符都能进行变化，匹配串中只包含$0/1$。

$\sum t_i\le 50,\sum |b_i|\le 100,n\le 100,2<G\le n+2$

---

解题思路

有匹配的问题，我们先拿所有的$c_i$出来建一棵AC自动机，然后考虑怎么计算每个字符能从哪个状态跳到哪个状态。

注意我们在AC自动机上走状态时不能走到包含匹配串的状态，这样我们可以将无论如何都包含匹配串视为最短不包含匹配串的长度无穷大。

那么我们考虑dp这个最短的长度，设$f_{i,s,t}$表示字符$i$经过变换后，能从状态$s$走到状态$t$的最短长度。

转移时我们考虑枚举一个变换$i$，再枚举一个起点$s$，然后设$g_{j,x}$表示现在走到$b_{i,j}$，在状态$x$时的最短长度，那么转移时就有
$$g_{j+1,y}=min\{g_{j,x}+f_{b_{i,j},x,y}\}$$

但是会注意到$f_{i,s,t}$之间的转移并不是一个单向的关系，会发现这是一个和最短路很类似的转移，我们考虑魔改一下SPFA。

我们先把$0,1$加入队列，然后每次取出队头$x$，我们把所有包含字符$x$的$b_i$都拿出来跑一次$g$，如果这次跑出来的$g$能够更新$f_{a_i,s,t}$，那么我们就把$a_i$入队（如果之前$a_i$不在队列中）。

我们视SPFA的复杂度为$O(n^2)$，记AC自动机状态数为$k$，每做一次转移应该是$O(|b_i|k^3)$，那么这题中SPFA的复杂度应该就是$O(G\sum |b_i|k^3)$，实际上跑起来常数会很小，可以通过本题。

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const ll N=105,inf=1e18;
ll G,n,m,a[N],f[N][N][N],g[N][52];
ll cnt,ch[N][2],fail[N];bool ed[N],v[N];
queue<int> q;vector<int> b[N],T[N];
void ins(ll n){
    
	ll x=0;
	for(ll i=1,c;i<=n;i++){
    
		scanf("%lld",&c);
		if(!ch[x][c])ch[x][c]=++cnt;
		x=ch[x][c];
	}
	ed[x]=1;return;
}
void getfail(){
    
	for(ll i=0;i<2;i++)
		if(ch[0][i])q.push(ch[0][i]);
	while(!q.empty()){
    
		ll x=q.front();q.pop();
		ed[x]|=ed[fail[x]];
		for(ll i=0;i<2;i++){
    
			if(ch[x][i]){
    
				fail[ch[x][i]]=ch[fail[x]][i];
				q.push(ch[x][i]);
			}
			else ch[x][i]=ch[fail[x]][i];
		}
	}
	return;
}
bool solve(int i){
    
	bool flag=0;
	for(ll s=0;s<=cnt;s++){
    
		if(ed[s])continue;
		memset(g,0x3f,sizeof(g));g[0][s]=0;
		for(ll j=0;j<b[i].size();j++){
    
			for(ll x=0;x<=cnt;x++){
    
				if(g[j][x]>=inf)continue;
				for(ll y=0;y<=cnt;y++)
					g[j+1][y]=min(g[j+1][y],g[j][x]+f[b[i][j]][x][y]);
			}
		}
		for(ll x=0;x<=cnt;x++){
    
			flag|=(g[b[i].size()][x]<f[a[i]][s][x]);
			f[a[i]][s][x]=min(f[a[i]][s][x],g[b[i].size()][x]);
		}
	}
	return flag;
} 
void SPFA(){
    
	q.push(0);q.push(1);v[0]=v[1]=1;
	while(!q.empty()){
    
		int x=q.front();q.pop();v[x]=0;
		for(int i=0;i<T[x].size();i++){
    
			int y=T[x][i];
			if(solve(y)&&!v[a[y]])
				q.push(a[y]),v[a[y]]=1;
		}
	}
	return;
}
signed main()
{
    
	scanf("%lld%lld%lld",&G,&n,&m);
	for(ll i=1,k;i<=n;i++){
    
		scanf("%lld%lld",&a[i],&k);
		for(ll j=1,x;j<=k;j++){
    
			scanf("%lld",&x),b[i].push_back(x);
			T[x].push_back(i);
		}
	}
	for(ll i=1,k;i<=m;i++){
    
		scanf("%lld",&k);
		ins(k);
	}
	getfail();ll k=0;
	memset(f,0x3f,sizeof(f));
	for(ll i=0;i<=cnt;i++){
    
		if(ed[i])continue;
		if(!ed[ch[i][0]])f[0][i][ch[i][0]]=1;
		if(!ed[ch[i][1]])f[1][i][ch[i][1]]=1;
	}
	SPFA();
	for(ll i=2;i<G;i++){
    
		ll ans=inf;
		for(ll x=0;x<=cnt;x++)
			ans=min(ans,f[i][0][x]);
		if(ans>=inf)puts("YES");
		else printf("NO %lld\n",ans);
	}
	return 0;
}