Description
Sulotion
首先要对每对咒语机建图，判断机器a是否能生成所有机器b生成的
如果跑一个相同的串，最后结束的点b可输出a不可输出，判断就为否
大概就用这种思路，f[x][y]表示a中跑到x b中跑到y是否可行，然后大概记忆化搜索，只有两种转移
//感觉跑自动机的题目经常要这么(跑到了哪一个结点)表示状态
建图之后可能会有环(a和b生成的一样)，于是强连通分量缩点
变成了DAG，然后dp记忆化搜索出答案
Code
一开始边的数组也直接用maxn了，最近怎么总是犯低级错误
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,maxm=1e4+; int S;
struct box{
int n,m,p[maxn][],ok[maxn];
}a[maxn];
int head[maxn],e[maxm],nxt[maxm],tot;
int adde(int u,int v){
e[++tot]=v,nxt[tot]=head[u];
head[u]=tot;
}
int low[maxn],pre[maxn],clock;
int scc[maxn],size[maxn],cnt,r[maxn],t; int c,d;
int vis[maxn][maxn];
int pd(int x,int y){
if(vis[x][y]) return ;
if(!a[c].ok[x]&&a[d].ok[y]) return ;
vis[x][y]=;
if(!pd(a[c].p[x][],a[d].p[y][])) return ;
if(!pd(a[c].p[x][],a[d].p[y][])) return ;
return ;
} int tarjan(int u){
pre[u]=low[u]=++clock;
r[++t]=u;
for(int i=head[u];i;i=nxt[i]){
int v=e[i];
if(!pre[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]){
low[u]=min(low[u],pre[v]);
}
}
if(pre[u]==low[u]){
++cnt;
while(t){
scc[r[t]]=cnt;
size[cnt]++;
if(r[t--]==u) break;
}
}
} int f[maxn],G[maxn][maxn];
int dfs(int u){
if(f[u]) return f[u];
int ret=;
for(int v=;v<=cnt;v++)
if(G[u][v]) ret=max(ret,dfs(v));
return f[u]=ret+size[u];
} int main(){
int x;
scanf("%d",&S);
for(int k=;k<=S;k++){
scanf("%d%d",&a[k].n,&a[k].m);
for(int i=;i<=a[k].m;i++)
scanf("%d",&x),a[k].ok[x+]=;
for(int i=;i<=a[k].n;i++){
scanf("%d%d",&a[k].p[i][],&a[k].p[i][]);
a[k].p[i][]++,a[k].p[i][]++;
}
} for(int i=;i<=S;i++)
for(int j=;j<=S;j++)
if(i!=j){
memset(vis,,sizeof(vis));
c=i,d=j;
if(pd(,)) adde(c,d);
} for(int i=;i<=S;i++)
if(!pre[i]) tarjan(i); for(int i=;i<=S;i++)
for(int j=head[i];j;j=nxt[j])
if(scc[i]!=scc[e[j]]) G[scc[i]][scc[e[j]]]=; int ans=;
for(int i=;i<=cnt;i++)
ans=max(ans,dfs(i)); printf("%d\n",ans);
return ;
}