[dfs][二进制状压] Luogu P4906 小奔关闹钟

偏执的太偏执、 2021-11-02 10:22 155阅读 0赞

# 题目描述 #

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

请你帮小奔求出最少开关次数，如果无论如何都不能关闭闹钟，请输出‘Change an alarm clock，please!’

# 题解 #

*  黑题？？？洛谷恶意评分
 *  状压后预处理按每一种开关后的情况bfs搜索情况就可以了

# 代码 #

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <queue>
     5 using namespace std;
     6 int n,m,b[5000000],a[25],d[25],bl[21][21];
     7 queue <int>Q;
     8 void bfs()
     9 {
    10     b[(1<<n)-1]=1,Q.push((1<<n)-1);
    11     while (Q.size())
    12     {
    13         int u=Q.front(); Q.pop();
    14         for (int i=1;i<=n;i++) if (!b[u^d[i]]) b[u^d[i]]=b[u]+1,Q.push(u^d[i]);
    15         if (b[0]) return;
    16     }
    17 }
    18 int main()
    19 {
    20     scanf("%d",&n);
    21     for (int i=1;i<=n;i++) 
    22     {
    23         memset(b,0,sizeof(b)),b[i]=1,scanf("%d",&m);
    24         for (int j=1,x;j<=m;j++) scanf("%d",&x),bl[i][x]=1;
    25     }
    26     for (int i=1;i<=n;i++)
    27     {
    28         d[i]^=(1<<(i-1));
    29         for (int j=1;j<=n;j++) 
    30             if (bl[i][j]&&i!=j)
    31             {
    32                 d[i]^=(1<<(j-1));
    33                 for (int k=1;k<=n;k++) if (bl[j][k]&&k!=j) d[i]^=(1<<(k-1));
    34             }
    35     }
    36     bfs();
    37     if (!b[0]) printf("Change an alarm clock，please!"); else printf("%d",b[0]-1);
    38 }

转载于:https://www.cnblogs.com/Comfortable/p/11245808.html