嗯,这题题目读了我好久啊
大概就是说,有若干个自动机,根据自动机的包含关系就能变成一个有向图,求图上的最长链
图上的最长链……很可惜只能DFS了。
现在要讲的是如何判断包含关系……额,这道题都是上个月做的了,还真有点忘了呢
我们用一个二元组(x,y)表示一个状态(即一号自动机在x点二号自动机在y点),刚开始状态是(0,0),然后BFS一下。
当且仅当存在x为输出源、y不为输出源且(x,y)状态被标记过时,一号自动机不被包含
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 60
#define MAXM 3600
#define x first
#define y second
using namespace std;
struct Box
{
int n,m,out[MAXN],p[MAXN][2];
bool flag[MAXN];
void Read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&out[i]);
flag[++out[i]]=true;
}
for(int i=1;i<=n;i++)
{
scanf("%d %d",&p[i][0],&p[i][1]);
p[i][0]++,p[i][1]++;
}
}
friend bool operator < (const Box &a,const Box &b)
{
static pair<int,int> queue[MAXM],head;
static bool use[MAXN][MAXN];
for(int i=1;i<=a.n;i++)
for(int j=1;j<=b.n;j++)
use[i][j]=false;
int front=0,rear=1;
queue[rear]=make_pair(1,1);
use[1][1]=true;
while(front<rear)
{
head=queue[++front];
if(a.flag[head.x]&&!b.flag[head.y]) return false;
for(int i=0;i<=1;i++)
{
int x=a.p[head.x][i],y=b.p[head.y][i];
if(use[x][y]) continue;
use[x][y]=true,queue[++rear]=make_pair(x,y);
}
}
return true;
}
}pandora[MAXN];
bool use[MAXN];
int n;
int tot,to[MAXM],next[MAXM],start[MAXN];
void make(int a,int b){ tot++,to[tot]=b,next[tot]=start[a],start[a]=tot; }
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
pandora[i].Read();
}
void Make_Graph()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&pandora[i]<pandora[j])
make(i,j);
}
bool DFS(int p,int dep,int n)
{
if(dep>n) return true;
use[p]=true;
for(int i=start[p];i;i=next[i])
if(use[to[i]]==false&&DFS(to[i],dep+1,n))
{
use[p]=false;
return true;
}
use[p]=false;
return false;
}
int Longest_Path()
{
int ans=0;
for(int i=1;i<=n;i++)
{
bool mark=false;
for(int j=1;j<=n&&mark==false;j++)
if(DFS(j,2,i))
mark=true;
if(mark==false) break;
ans=i;
}
return ans;
}
int main()
{
read();
Make_Graph();
printf("%d\n",Longest_Path());
return 0;
}
评论