P4906 小奔关闹钟

题目背景

由于今天是星期一，闹钟准时响了，由于小奔太困了，所以她想关停闹钟。

题目描述

可是，他的闹钟电路太复杂了，有很多个开关，每个开关都连着其他开关，其他开关又连着更多的开关，当且仅当所有开关都关闭时，闹钟才会停止响铃，（初始时默认每个开关都开着的），她该如何是好呢？

请你帮小奔求出最少开关次数，如果无论如何都不能关闭闹钟，请输出‘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： 复制

说明

样例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);

}

巴特西

P4906 小奔关闹钟

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章