P2962 [USACO09NOV]灯Lights 对抗搜索

\(\color{#0066ff}{题目描述}\)

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏! 牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个非常複杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边连接两盏灯。 每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开著的时候,这盏灯被关掉;当一盏灯是关著的时候,这盏灯被打开。 问最少要按下多少个开关,才能把所有的灯都给重新打开。 数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。

\(\color{#0066ff}{输入格式}\)

  • Line 1: Two space-separated integers: N and M.

  • Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.

\(\color{#0066ff}{输出格式}\)

  • Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

\(\color{#0066ff}{输入样例}\)

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

\(\color{#0066ff}{输出样例}\)

3

\(\color{#0066ff}{题解}\)

看n的范围,显然可以对抗搜索

用\(O(2^n)\)枚举出前半部分的点选或不选,并记录到达状态的最小步数(用map)

再搜后半部分点选或不选,只要能跟刚刚的拼上,就更新答案

#include<cstdio>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<map>
#define _ 0
#define LL long long
#define Space putchar(' ')
#define Enter putchar('\n')
#define fuu(x,y,z) for(int x=(y),x##end=z;x<=x##end;x++)
#define fu(x,y,z) for(int x=(y),x##end=z;x<x##end;x++)
#define fdd(x,y,z) for(int x=(y),x##end=z;x>=x##end;x--)
#define fd(x,y,z) for(int x=(y),x##end=z;x>x##end;x--)
#define mem(x,y) memset(x,y,sizeof(x))
#ifndef olinr
inline char getc()
{
static char buf[100001],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;
}
#else
#define getc() getchar()
#endif
template<typename T>inline void in(T &x)
{
int f=1; char ch; x=0;
while(!isdigit(ch=getc()))(ch=='-')&&(f=-f);
while(isdigit(ch)) x=x*10+(ch^48),ch=getc();
x*=f;
}
int n,m;
std::map<LL,int> mp;
LL zt[55];
int mid;
int ans=0x7fffffff;
inline void dfs1(int now,LL z,int step)
{
if(now==mid+1)
{
if(!mp.count(z)) mp[z]=step;
else mp[z]=std::min(mp[z],step);
return;
}
dfs1(now+1,z^zt[now],step+1);
dfs1(now+1,z,step);
}
inline void dfs2(int now,LL z,int step)
{
if(now==n+1)
{
if(mp.count(z)) ans=std::min(ans,step+mp[z]);
return;
}
dfs2(now+1,z^zt[now],step+1);
dfs2(now+1,z,step);
}
int main()
{
in(n),in(m);
int x,y;
fuu(i,1,m) in(x),in(y),zt[x]|=1LL<<(y-1),zt[y]|=1LL<<(x-1);
fuu(i,1,n) zt[i]|=(1<<(i-1));
mid=(1+n)>>1;
dfs1(1,(1LL<<n)-1,0);
dfs2(mid+1,0LL,0);
printf("%d",ans);
return ~~(0^_^0);
}
上一篇:Razor视图


下一篇:JS学习笔记:(二)回流和重绘