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

ydc的博客

 
 
 

日志

 
 

CTSC 2013 复原  

2014-03-13 21:10:10|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实写题解是挺累的……
这题正解很屌……但是爆搜直接就过了
第二问是最大独立集,我本想写手套的那个剪枝的,发现2^n爆搜能过,无语了
第一问我看了vfleaking的代码……两个优化,一个BFS出每个联通块,对联通块进行DFS,另一个是位运算
至于枚举的姿势我也是看了vfleaking的……就是枚举一条弦的两个端点的位置
这竟然能过……
接下来的题解等A完了再补吧

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lowbit(x) x&-x
#define maxn 50
using namespace std;
bool ori[maxn][maxn];
int mat[maxn],n,len,Log[1<<20];
int queue[maxn],seq[maxn];
void read()
{
int m;
scanf("%d %d",&n,&m);
for(int i=1,a,b;i<=m;++i)
{
scanf("%d %d",&a,&b);
ori[a][b]=ori[b][a]=true;
}
for(int i=0;i<n;++i)
Log[1<<i]=i+1;
}
bool DFS(int p,int lim)
{
if(p>lim)
return true;
++len;
for(int i=len;i>1;--i)
seq[i]=seq[i-1];
for(int i=1;i<=len;++i)
{
seq[i]=p,++len;
for(int j=len;j>i+1;--j)
seq[j]=seq[j-1];
int s=0;
for(int j=i+1;j<=len;++j)
{
seq[j]=p;
int x=(mat[p]&((1<<p)-1))^s;
if(x==0&&DFS(p+1,lim))
return true;
seq[j]=seq[j+1];
s=1<<(seq[j]-1)^s;
}
--len;
seq[i]=seq[i+1];
}
--len;
return false;
}
bool check(int S)
{
for(int i=S;i;i-=lowbit(i))
{
int x=Log[lowbit(i)];
for(int j=S;j!=i;j-=lowbit(j))
if(ori[x][Log[lowbit(j)]])
return false;
}
return true;
}
void work()
{
static bool use[maxn];
static int ans[maxn];
int top=0;
for(int i=1;i<=n;++i)
if(use[i]==false)
{
int front=0,rear=1;
queue[rear]=i,use[i]=true;
while(front<rear)
{
int p=queue[++front];
for(int j=1;j<=n;++j)
if(use[j]==false&&ori[p][j])
{
queue[++rear]=j;
use[j]=true;
}
}
for(int i=1;i<=rear;++i)
{
mat[i]=0;
int p=queue[i];
for(int j=1;j<=rear;++j)
if(ori[p][queue[j]])
mat[i]=1<<(j-1)|mat[i];
}
len=0;
DFS(1,rear);
for(int j=1;j<=len;++j)
ans[++top]=queue[seq[j]];
}
for(int i=1;i<=top;++i)
printf("%d%c",ans[i],i<top?' ':'\n');
int maxv=0;
for(int i=1;i<(1<<n);++i)
{
int tot=0;
for(int j=i;j;j-=lowbit(j))
++tot;
if(tot<=maxv)
continue;
if(check(i))
maxv=tot;
}
printf("%d\n",maxv);
}
int main()
{
read();
work();
return 0;
}

  评论这张
 
阅读(479)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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