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

ydc的博客

 
 
 

日志

 
 

bzoj 1194 (hnoi2006) 潘多拉的盒子  

2013-03-27 23:31:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
嗯,这题题目读了我好久啊
大概就是说,有若干个自动机,根据自动机的包含关系就能变成一个有向图,求图上的最长链
图上的最长链……很可惜只能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; }
  评论这张
 
阅读(397)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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