P6698-[balticoi 2020 day2] virus [AC automata, DP, SPFA]

On the subject

Topic link :https://www.luogu.com.cn/problem/P6698

---

The main idea of the topic

There is a $0\sim G-1$ Character set for , Among them is $n$ Two transformations , Be able to put a character $a_i(a_i>1)$ Become a string of characters $b_i$, When only... Is left in a string $0$ and $1$ The hour shift is over .

Then give $m$ Matching strings $c_i$. Now for each character $i\in [2,G-1]$, Character or not $i$ It contains at least one matching string at the end of the change , If not , Find the shortest final string length that does not contain any matching strings .

Make sure that everyone is in $[2,G-1]$ All characters can be changed , The matching string contains only $0/1$.

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

---

Their thinking

There are matching problems , Let's take all of them first $c_i$ Come out and build one AC automata , Then consider how to calculate which state each character can jump from .

Notice that we are AC An automaton cannot go to a state containing a matching string when it goes to a state , In this way, we can regard including matching string as the shortest length without matching string is infinite .

So let's consider dp The shortest length , set up $f_{i,s,t}$ According to the character $i$ After transformation , From the State $s$ Go to status $t$ The shortest length of .

When transferring, we consider enumerating a transformation $i$, Enumerate another starting point $s$, Then set $g_{j,x}$ It means to go to now $b_{i,j}$, In state $x$ The shortest length of time , Then there is
$$g_{j+1,y}=min\{g_{j,x}+f_{b_{i,j},x,y}\}$$

But you will notice $f_{i,s,t}$ The transfer between is not a one-way relationship , You will find that this is a transfer very similar to the shortest path , Let's consider a magic change SPFA.

Let's put the $0,1$ Join the queue , Then take out the team leader each time $x$, We put all containing characters $x$ Of $b_i$ Take them out and run once $g$, If you come out this time $g$ Be able to update $f_{a_i,s,t}$, Then we will $a_i$ The team （ If before $a_i$ Not in line ）.

We see SPFA The complexity of is $O(n^2)$, remember AC The number of automata States is $k$, Each transfer should be $O(|b_i|k^3)$, So in this question SPFA The complexity of should be $O(G\sum |b_i|k^3)$, In fact, the running constant will be very small , Can pass this problem .

---

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;
}