[HNOI2006]潘多拉的宝盒

https://www.zybuluo.com/ysner/note/1250303

题面

给定\(s\)个自动机，如果某个自动机\(A\)能产生的所有串都能在自动机\(B\)中产生(即走相同\(0/1\)路径后，同时碰到输出元），则称\(B\)是\(A\)的一个升级，求最长升级序列长度。

\(s,n\leq50\)

解析

辣鸡题目考语文

然而看懂题后还是很简单的。

判断\(B\)是否为\(A\)的升级，就每次分别在\(A,B\)走相同的\(0/1\)路径（因每个点有两个出度），若在\(A\)碰到一个输出元，而此时\(B\)没有，就说明不是升级。

是升级就把\(A->B\)边权赋为\(1\)。

最后\(Floyd\)跑最长路即可。

（或者建边+拓扑排序也可以）。

但要注意，如果有两个完全相同的自动机，两者都会判为对方的升级，这时需强制只有一个方向边权赋为\(1\)（建边的话跑\(Tarjan\)缩点）。

没清空queue调了?h

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define ll long long

#define re register

#define il inline

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a);(b))

#define N 100

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

int s,n,m,h[N],out[N][N],a[N][N][2],dis[N][N];

ll ans;

bool vis[N][N];

struct node{int x,y;};

queue<node>Q;

il int gi()

{

    re int x=0,t=1;

    re char ch=getchar();

    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

    if(ch=='-') t=-1,ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*t;

}

il int check(re int s1,re int s2)

{

  //printf("!!!%d %d\n",s1,s2);

  while(!Q.empty()) Q.pop();

    memset(vis,0,sizeof(vis));

    Q.push((node){1,1});

    while(!Q.empty())

    {

        re node now=Q.front(),tmp;Q.pop();//gg

    if(out[s1][now.x]&&!out[s2][now.y]) return 0;

      tmp.x=a[s1][now.x][0];tmp.y=a[s2][now.y][0];

  	if(!vis[tmp.x][tmp.y]) vis[tmp.x][tmp.y]=1,Q.push(tmp);

        tmp.x=a[s1][now.x][1];tmp.y=a[s2][now.y][1];

  	if(!vis[tmp.x][tmp.y]) vis[tmp.x][tmp.y]=1,Q.push(tmp);

    }

    return 1;

}

int main()

{

    s=gi();

    fp(i,1,s)

    {

        n=gi();m=gi();

    //fp(j,1,n) a[i][j][0]=a[i][j][1]=1;

        fp(j,1,m) out[i][gi()+1]=1;

        fp(j,1,n)

        {

            re int u=gi()+1,v=gi()+1;

            a[i][j][0]=u;a[i][j][1]=v;

        }

    }

    memset(dis,-63,sizeof(dis));

    fp(i,1,s)

        fp(j,1,s)

      if(i!=j&&check(i,j)&&dis[j][i]<0) dis[i][j]=1;//注意到有完全相同的自动机

    //fp(i,1,s) fp(j,1,s) printf("%d %d %d\n",i,j,dis[i][j]);

    fp(k,1,s)

        fp(i,1,s)

      fp(j,1,s)

      //if(dis[i][j]<dis[i][k]+dis[k][j]&&dis[i][k]&&dis[k][j]

        dis[i][j]=max(dis[i][j],dis[i][k]+dis[k][j]),ans=max(ans,dis[i][j]);

    printf("%lld\n",ans+1);

    return 0;

}

巴特西

[HNOI2006]潘多拉的宝盒

https://www.zybuluo.com/ysner/note/1250303

题面

解析

最新文章

热门文章