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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1770][Usaco2009 Nov]lights 灯  

2014-10-15 13:09:54|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1770: [Usaco2009 Nov]lights

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 383  Solved: 185
[Submit][Status]

Description

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐, 痛苦与绝望。

她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个非常复杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边连接两盏灯。每盏灯上面都带有一个开关。

当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开着的时候,这盏灯被关掉;当一盏灯是关着的时候,这盏灯被打开。问最少要按下多少个开关,才能把所有的灯都给重新打开。数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。

Input

第一行:两个空格隔开的整数:N和M

第二到第M+1行:每一行有两个由空格隔开的整数,表示两盏灯被一条无向边连接在一起。没有一条边会出现两次。

Output

第一行:一个单独的整数,表示要把所有的灯都打开时,最少需要按下的开关的数目。

Sample Input

5 6
1 2
1 3
4 2
3 4
2 5
5 3

输入:一共5盏灯。灯1、灯4和灯5都连接着灯2和灯3。

Sample Output

3

输出:按下在灯1、灯4和灯5上面的开关。

Solution

一眼异或方程组。

有一些灯的状态是确定的,可以先用异或方程组算出来,并且能得到答案的上界(不确定的都不选)。

剩下那些不确定的,再去跑暴力。加一个剪枝,如果当前开的灯数大等于ans就break。

比折半搜索不知道快到哪里去了。。。

Code

/**************************************************************
    Problem: 1770
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:824 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
int la[40],et,n,m,i,j,k,ans,now;long long a[40],tmp;
bool cmp(long long i,long long j){return i>j;}
struct E{int to,nxt;}e[2000];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(int xx,int now)
{
    if(now>=ans)return;
    if(xx==0){ans>now?ans=now:1;return;}
    long long b=a[xx];
    for(int i=xx+1;i<=n;i++)
    if(a[xx]&(1LL<<(n+1-i)))a[xx]^=a[i];
    if(a[xx]&(1LL<<(n+1-xx)))dfs(xx-1,now+(a[xx]&1));
    else if(~a[xx]&1)
    a[xx]|=1LL<<(n+1-xx),dfs(xx-1,now+(a[xx]&1)),
    a[xx]^=1,dfs(xx-1,now+(a[xx]&1));
    a[xx]=b;
}
char ch;int aa;int F(){
    while(ch=getchar(),ch<48||ch>57);aa=ch-48;
    while(ch=getchar(),ch>47&&ch<58)aa=aa*10+ch-48;return aa;
}
int main()
{
    for(n=F(),m=F(),i=1;i<=m;i++)j=F(),k=F(),add(j,k),add(k,j);
    for(i=1;i<=n;i++)
    for(a[i]=(1LL<<i)+1,j=la[i];j;j=e[j].nxt)a[i]+=1LL<<e[j].to;
    for(i=1;i<=n;i++)if(std::sort(a+i,a+n+1,cmp),a[i]&(tmp=1LL<<(n+1-i)))
    for(j=i+1;j<=n;j++)if(tmp&a[j])a[j]^=a[i];
    for(i=n-1;i;i--)
    for(j=1;j<n+1-i;j++)
    if((a[i]&(tmp=1LL<<j))&&(a[n+1-j]&tmp))a[i]^=a[n+1-j];
    for(i=1;i<=n;i++)ans+=(a[i]&1);
    dfs(n,0);printf("%d\n",ans);
}
  评论这张
 
阅读(273)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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