题面：洛谷传送门 BZOJ传送门
标签里三个算法全都是提高组的，然而..这是一道神题
我们把这道题分为两个部分解决
1.找出所有咒语机两两之间的包含关系
2.求出咒语机的最长上升序列
我们假设咒语机$a,b$满足$a\in b$
如果这个条件不成立，说明存在一个串$S$，$a$能输出，$b$不能输出
一个咒语机能产生的字符串可能是无限长的，直接枚举字符串肯定不行
考虑转化问题
我们构造另外一个图，图中每个点是一个二元组$(x,y)$
我们暴力枚举咒语机$a$中的一个元件$x$，$b$中的一个元件$y$
我们把$(x,y)$分别向$(p_{x,0},p_{y,0}),(p_{x,1},p_{y,1})$连边
如果从$(0,0)$开始，走到了一个节点$(x,y)$，且$x$是$S$的一个输出点，而$y$却不是
说明$a\in b$不成立
因为从$(0,0)$走到$(x,y)$这样一条路径，对于$a,b$来说，是它们都能表示出来的字符串
即$a$中从$0$号元件走到$x$，$b$中从$0$号元件走到$y$，它们走出来的路径表示的字符串相同
而$a$能把它输出，$b$却不能，那么一定不满足$a\in b$
我们解决了第一个部分
我们得到了咒语机(点的集合)之间的关系，现在我们要求出它的最长上升序列
拓扑排序裸题吧
然而可能会出现环，即某些咒语机能表示出来的字符串集合相同
用$tarjan$缩点重新建出拓扑图，拓扑排序跑最长路即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 2505
#define M1 55
using namespace std; struct Graph{
int p[M1][],out[M1],n,m;
void Read()
{
int i,x;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++) scanf("%d",&x),out[x+]=;
for(i=;i<=n;i++) scanf("%d%d",&p[i][],&p[i][]),p[i][]++,p[i][]++;
}
}g[M1];
struct Edge{
int head[N1],nxt[N1<<],to[N1<<],cte;
void ae(int u,int v){ cte++; to[cte]=v; nxt[cte]=head[u]; head[u]=cte; }
}e,E,N; int nt[N1],que[N1],hd,tl,vis[N1],inc[M1];
void init()
{
memset(&e,,sizeof(e));
memset(nt,,sizeof(nt));
memset(vis,,sizeof(vis));
}
int solve(Graph &ss,Graph &tt)
{
int i,j,x,v,ans=-; init();
for(i=;i<=ss.n;i++)
for(j=;j<=tt.n;j++)
{
x=(i-)*tt.n+j;
v=(ss.p[i][]-)*tt.n+tt.p[j][]; e.ae(x,v);
v=(ss.p[i][]-)*tt.n+tt.p[j][]; e.ae(x,v);
if(ss.out[i]&&!tt.out[j]) nt[x]=;
if(!ss.out[i]&&tt.out[j]) nt[x]=-;
}
hd=,tl=; que[++tl]=; vis[]=;
while(hd<=tl)
{
x=que[hd++];
if(nt[x])
{
if(ans==-) ans=nt[x];
else if(ans!=nt[x]) return ;
}
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j];
if(!vis[v]) que[++tl]=v, vis[v]=;
}
}
return ans;
}
int low[M1],dfn[M1],use[M1],stk[M1],tim,tp;
int num[M1],nn,dad[M1],f[M1];
void tarjan(int x,int fa)
{
int j,v;
low[x]=dfn[x]=++tim;
stk[++tp]=x; use[x]=;
for(j=E.head[x];j;j=E.nxt[j])
{
v=E.to[j];
if(v==fa) continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
}else if(use[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(low[x]==dfn[x])
{
nn++;
while(stk[tp]!=x)
{
use[stk[tp]]=,dad[stk[tp]]=nn;
tp--,num[nn]++;
}
dad[x]=nn, use[x]=, tp--, num[nn]++;
}
} int S; int main()
{
scanf("%d",&S);
int i,j,k,s,sx,sy,x,v,ans=;
for(s=;s<=S;s++) g[s].Read();
for(sx=;sx<=S;sx++)
for(sy=sx+;sy<=S;sy++)
{
k=solve(g[sx],g[sy]);
if(!k) continue;
if(ans==-) E.ae(sx,sy), E.ae(sy,sx);
else if(k==-) E.ae(sx,sy);
else E.ae(sy,sx);
}
for(s=;s<=S;s++)
if(!dfn[s]) tarjan(s,-);
for(x=;x<=S;x++)
for(j=E.head[x];j;j=E.nxt[j])
{
v=E.to[j];
if(dad[x]!=dad[v])
N.ae(dad[x],dad[v]), inc[dad[v]]++;
}
hd=,tl=;
for(i=;i<=nn;i++) if(!inc[i]) que[++tl]=i;
memset(use,,sizeof(use));
while(hd<=tl)
{
x=que[hd++]; ans=max(ans,f[x]);
for(j=N.head[x];j;j=N.nxt[j])
{
v=N.to[j];
f[v]=max(f[v],f[x]+); inc[v]--;
if(!inc[v]) que[++tl]=v;
}
}
printf("%d\n",ans+);
}