题意：
s个DFA，选出尽量多的自动机a0, a1, a2, . . . , at，使得a1包含a0、a2包 含a1，以此类推。s ≤ 50。
DFA的字符集为{0,1}，有的节点是输出源，节点数n ≤ 50。
判断出包含关系后就是裸的最长路，求$SCC$后$DP$就好了
重点在判断包含：
$n$实在太小了，我们直接枚举所有的自动机，然后两个同时从起点开始$bfs$所有情况看看是否在某个状态一个有输出另一个没有
复杂度$O(n^4)$
注意：
$Candy?$这个沙茶$bfs$没有判断$(0,0)$状态是否一个输出一个不输出$WA$了好久，并且他还有一次求$SCC$没有枚举所有点
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N=55; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int s,n,m; struct DFA{ int n,m,p[N][2],out[N]; }a[N]; struct edge{ int v,ne; }e[N*N<<1],e2[N*N<<1]; int h[N],cnt,h2[N],cnt2; inline void ins(int u,int v){//printf("ins %d %d %d ",cnt,u,v); cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; } inline void ins2(int u,int v){//printf("ins2 %d %d ",u,v); edge *e=e2;int *h=h2,&cnt=cnt2; cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; } struct node{ int x,y; node(int a=0,int b=0):x(a),y(b){} }q[N*N]; int head,tail; bool vis[N][N]; void bfs(DFA &a,DFA &b,int i,int j){ int a_b=1,b_a=1; memset(vis,0,sizeof(vis)); head=tail=1; q[tail++]=node(0,0);vis[0][0]=1; while(head!=tail){ node u=q[head++]; int x=u.x , y=u.y; if(a.out[x]&&!b.out[y]) b_a=0; if(!a.out[x]&&b.out[y]) a_b=0; if(a_b==0&&b_a==0) break; for(int i=0;i<=1;i++){ int nx=a.p[x][i],ny=b.p[y][i]; if(!vis[nx][ny]){ vis[nx][ny]=1; q[tail++]=node(nx,ny); } } } if(a_b==1) ins(i,j); else if(b_a==1) ins(j,i); } void buildGraph(){ for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) bfs(a[i],a[j],i,j); } int dfn[N],dfc,low[N],scc,belong[N]; int st[N],top; int val[N]; void dfs(int u){ dfn[u]=low[u]=++dfc; st[++top]=u; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ dfs(v); low[u]=min(low[u],low[v]); }else if(!belong[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ scc++; while(true){ int x=st[top--]; belong[x]=scc; val[scc]++; if(x==u) break; } } } int f[N]; int dp(int u,int fa){ if(f[u]) return f[u]; for(int i=h2[u];i;i=e2[i].ne) if(e2[i].v!=fa) f[u]=max(f[u],dp(e2[i].v,u)); return f[u]+=val[u]; } int main(){ //freopen("in","r",stdin); n=read(); for(int i=1;i<=n;i++){ a[i].n=read();a[i].m=read(); for(int j=1;j<=a[i].m;j++) a[i].out[read()]=1; for(int j=0;j<a[i].n;j++) a[i].p[j][0]=read(),a[i].p[j][1]=read(); } buildGraph(); for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); for(int u=1;u<=n;u++) for(int i=h[u];i;i=e[i].ne) if(belong[u]!=belong[e[i].v]) ins2(belong[u],belong[e[i].v]); int ans=0; for(int i=1;i<=scc;i++) ans=max(ans,dp(i,0)); printf("%d ",ans); }