Description
Sulotion
首先要对每对咒语机建图，判断机器a是否能生成所有机器b生成的
如果跑一个相同的串，最后结束的点b可输出a不可输出，判断就为否
大概就用这种思路，f[x][y]表示a中跑到x b中跑到y是否可行，然后大概记忆化搜索，只有两种转移
//感觉跑自动机的题目经常要这么(跑到了哪一个结点)表示状态
建图之后可能会有环(a和b生成的一样)，于是强连通分量缩点
变成了DAG，然后dp记忆化搜索出答案
Code
一开始边的数组也直接用maxn了，最近怎么总是犯低级错误
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=55,maxm=1e4+5; 6 7 int S; 8 struct box{ 9 int n,m,p[maxn][2],ok[maxn];10 }a[maxn];11 int head[maxn],e[maxm],nxt[maxm],tot;12 int adde(int u,int v){13 e[++tot]=v,nxt[tot]=head[u];14 head[u]=tot;15 }16 int low[maxn],pre[maxn],clock;17 int scc[maxn],size[maxn],cnt,r[maxn],t;18 19 int c,d;20 int vis[maxn][maxn];21 int pd(int x,int y){22 if(vis[x][y]) return 1;23 if(!a[c].ok[x]&&a[d].ok[y]) return 0;24 vis[x][y]=1;25 if(!pd(a[c].p[x][0],a[d].p[y][0])) return 0;26 if(!pd(a[c].p[x][1],a[d].p[y][1])) return 0;27 return 1;28 }29 30 int tarjan(int u){31 pre[u]=low[u]=++clock;32 r[++t]=u;33 for(int i=head[u];i;i=nxt[i]){34 int v=e[i];35 if(!pre[v]){36 tarjan(v);37 low[u]=min(low[u],low[v]);38 }39 else if(!scc[v]){40 low[u]=min(low[u],pre[v]);41 }42 }43 if(pre[u]==low[u]){44 ++cnt;45 while(t){46 scc[r[t]]=cnt;47 size[cnt]++;48 if(r[t--]==u) break;49 }50 }51 }52 53 int f[maxn],G[maxn][maxn];54 int dfs(int u){55 if(f[u]) return f[u];56 int ret=0;57 for(int v=1;v<=cnt;v++)58 if(G[u][v]) ret=max(ret,dfs(v));59 return f[u]=ret+size[u];60 }61 62 int main(){63 int x;64 scanf("%d",&S);65 for(int k=1;k<=S;k++){66 scanf("%d%d",&a[k].n,&a[k].m);67 for(int i=1;i<=a[k].m;i++)68 scanf("%d",&x),a[k].ok[x+1]=1;69 for(int i=1;i<=a[k].n;i++){70 scanf("%d%d",&a[k].p[i][0],&a[k].p[i][1]);71 a[k].p[i][0]++,a[k].p[i][1]++;72 }73 }74 75 for(int i=1;i<=S;i++)76 for(int j=1;j<=S;j++)77 if(i!=j){78 memset(vis,0,sizeof(vis));79 c=i,d=j;80 if(pd(1,1)) adde(c,d);81 }82 83 for(int i=1;i<=S;i++)84 if(!pre[i]) tarjan(i);85 86 for(int i=1;i<=S;i++)87 for(int j=head[i];j;j=nxt[j])88 if(scc[i]!=scc[e[j]]) G[scc[i]][scc[e[j]]]=1;89 90 int ans=0; 91 for(int i=1;i<=cnt;i++)92 ans=max(ans,dfs(i));93 94 printf("%d\n",ans);95 return 0;96 }