题目背景
由于今天是星期一,闹钟准时响了,由于小奔太困了,所以她想关停闹钟。
题目描述
可是,他的闹钟电路太复杂了,有很多个开关,每个开关都连着其他开关,其他开关又连着更多的开关,当且仅当所有开关都关闭时,闹钟才会停止响铃,(初始时默认每个开关都开着的),她该如何是好呢?
请你帮小奔求出最少开关次数,如果无论如何都不能关闭闹钟,请输出‘Change an alarm clock,please!’
输入输出格式
输入格式:
共有N+1行
第一行一个数N(1≤N≤20),表示有N个开关,从第2行起的第i行表示第i个闹钟开关。
以后N行,每行第一个数为M(0≤M≤N-1),表示第i个闹钟开关的直接关联开关个数。(由直接关联开关所关联的直接关联开关,自然就是第i个闹钟间接关联开关啦,当打开第i个开关时,只有直接关联,间接关联以及第i个开关才会起作用。),之后M个数,表示第i个闹钟直接关联开关的标号。(如果M为0则表示没有任何关联)
输出格式:
一个数ans,表示最少按开关次数,如果无法关闭,输出‘Change an alarm clock,please!’
输入输出样例
输入样例#1: 复制
5
4 2 3 4 5
2 1 3
2 1 4
2 1 5
1 1
输出样例#1: 复制
2
说明
样例1说明:
先关闭5,直接关联会关闭1。1间接关闭2、3、4,但会重新打开5。
此时共关闭开关一次,已关闭1,2,3,4
再打开2,直接关联会打开1和3。1间接关闭2、3、5,重新打开4。3间接关闭1、4。
此时共关闭开关2次,已关闭1,2,3,4,5,彻底关闭闹钟。
sb题+卡读入==黑体????
二进制状压,预处理按每一种开关后的情况bfs搜索情况0即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
#define max(a,b) ((a)>(b)? (a):(b))
#define min(a,b) ((a)<(b)? (a):(b))
using namespace std;
int b[5000000],i,m,n,j,k,a[25],d[25],bl[21][21],x;
queue <int>q;
void bfs()
{
b[(1<<n)-1]=1;
q.push((1<<n)-1);
while(q.size())
{
int t=q.front(); q.pop();
for(int i=1;i<=n;i++)
{
if(!b[t^d[i]])
{
b[t^d[i]]=b[t]+1;
q.push(t^d[i]);
}
}
if(b[0]) return;
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
b[i]=1;
scanf("%d",&m);
for(j=1;j<=m;++j)
{
scanf("%d",&x);
bl[i][x]=1;
}
}
for(i=1;i<=n;++i)
{
d[i]^=(1<<(i-1));
for(j=1;j<=n;++j) if(bl[i][j] && i != j)
{
d[i]^=(1<<(j-1));
for(k = 1; k <= n; ++k) if(bl[j][k] && k != j)
d[i]^=(1<<(k-1));
}
}
bfs();
if(b[0]==0) printf("Change an alarm clock,please!");
else printf("%d",b[0]-1);
}