注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 
关于我
文章分类
网易考拉推荐
GACHA精选

HNOI 2006 day2 潘多拉的盒子 ( bzoj 1194 ) 判断自动机的包含关系  

2014-04-14 12:41:54|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题的重点是如何判断两个自动机的包含关系 如果会判断两个自动机是否等价 这个问题便也可以很轻松地解决了
记得校内考试时 由于当时不会判断自动机等价对于这道题我是用限制字符串长度来判断的 
复杂度为 O(s^2*2^L)L为字符串长度 由于hnoi数据较水 这样还可以混到60pts 不过其实正解也不是很难
vfk说判断自动机等价是WC上qmd讲过的(看来当时没听懂 后来也没再看看讲义的我还是只能再学习下了)
---------------------------------------------------------------------------------------------------------------------------------
膜拜了YDC的二元组的方法(或许就是标准方法)
在两个自动机上一起模拟生成字符串(bfs、dfs均可) 走过的要标记一下
如果在A上处于不可输出点 而在B上处于可输出点 那么B就绝对不包含与A了
如果全部走完了还是没有判断出上述状态 那么B就包含于A
这样判断自动机的包含关系就可以以O(s^2*n^2)解决了
---------------------------------------------------------------------------------------------------------------------------------
至于求最长序列 也就是最长路 标准的做法是缩环——由于这是个偏序集(表示vfk告诉我以前从未听过偏序集。。。)  然后再DP,这样就是O(s)解决了
不过考虑到s只有50 而且hnoi一般不会用特殊数据卡(也就是说有不错的期望的时间的话 实际上便能很快出界了) 所以就懒得再写个缩环了 直接dfs求最长路——数据较弱 果然瞬间出解。。。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=55;
int aim[N][N][2],used[N][N];
int firste[N],nexte[N*N],v[N*N],dist[N],fa[N];
int ans[N];
bool canout[N][N];
bool indfs[N];
int s,n,m,t=0;
int e=0,maxdist=0,maxnode;
bool check(int aa,int bb,int x,int y)
{
if(used[x][y]==t)return 1;
if((!canout[aa][x])&&(canout[bb][y]))return 0;
used[x][y]=t;
if(!check(aa,bb,aim[aa][x][0],aim[bb][y][0]))return 0;
if(!check(aa,bb,aim[aa][x][1],aim[bb][y][1]))return 0;
return 1;
}
void build_edge(int x,int y)
{
++e;
nexte[e]=firste[x];
firste[x]=e;
v[e]=y;
}
void spfa(int u)
{
indfs[u]=1;
for(int p=firste[u];p;p=nexte[p])
{
if(!indfs[v[p]]&&dist[v[p]]<=dist[u])
{
dist[v[p]]=dist[u]+1;
fa[v[p]]=u;
spfa(v[p]);
}
}
indfs[u]=0;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int x,y;
scanf("%d",&s);
rep(i,s)
{
scanf("%d%d",&n,&m);
rep(j,m)
{
scanf("%d",&x);
++x;
canout[i][x]=1;
}
rep(j,n)
{
scanf("%d%d",&x,&y);
++x;++y;
aim[i][j][0]=x;
aim[i][j][1]=y;
}
}
rep(i,s)
rep(j,s)
if(i!=j)
{
++t;
if(check(i,j,1,1))
build_edge(j,i);
}
rep(i,s)build_edge(0,i);
spfa(0);
rep(i,s)
if(dist[i]>maxdist)
{
maxdist=dist[i];
maxnode=i;
}
int num=maxdist+1;
while(maxnode)
{
ans[--num]=maxnode-1;
maxnode=fa[maxnode];
}
printf("%d\n",maxdist);
rep(i,maxdist)
printf("%d ",ans[i]);
return 0;
}



  评论这张
 
阅读(136)| 评论(11)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017