BZOJ 1194: [HNOI2006]潘多拉的盒子 [DP DFA]

传送门

题意：

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\n",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\n",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\n",ans);
}