【日常学习】【状压BFS】codevs2594 解药还是毒药题解

心已赠人 2022-08-09 17:38 64阅读 0赞

题目描述 Description

Smart研制出对付各种症状的解药，可是他一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症（你可能会问那…那是解药还是毒药啊？）……，经过Smart的努力，终于弄清了每种药的具体性能，他会把每种药能治愈的病症和能使人患上的病症列一张清单给你，然后你要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声，病症的数目不超过10种，而且他的药是用不完的，就是说每种药剂都可以被重复使用。

输入描述 Input Description

给你们的单子里第一行是病症的总数n（1≤n≤10）。第二行是药剂的种类m（0<m≤100）。

以下有m行，每行有n个数字用空格隔开，文件的第i+2行的n个数字中，如果第j个数为1，就表示第i种药可以治愈病症j（如果患有这种病的话则治愈，没有这种病则无影响），如果为0表示无影响，如果为\-1表示反而能使人得上这种病（无病患上，有病无影响）。Smart制的药任何两种性能都不同。

输出描述 Output Description

你只要输出用的最少的药剂数就可以了，其实还有可能用尽了所有的药也不能将所有病治愈，那样的话你们只要输出“The patient will be dead.”就可以了。

样例输入 Sample Input

1 0 1

\-1 1 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1≤n≤10

0<m≤100

洛谷月赛的关灯问题II

之前传球游戏也使用了状压

在这里不再赘述 具体看自己写的状压DP、位运算和逻辑运算学习手记

这篇文章大概NOIP结束后 我会放到博客上。

对于这道题目，只需注意两个操作：

k^(1 << i)状态k的第i位取反 k&(1 << i)判断i是否为真，真返回true

代码

//codevs2594 解药还是毒药 状压bfs 
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             using namespace std; const int maxn=12; const int maxm=100+10; int a[maxm][maxn];//第i个开关对于第j个灯的效果 int dist[1<<11]; int n,m; bool inq[1<<11]; queue
            
              q; void bfs(int x) { memset(inq,0,sizeof(inq)); memset(dist,0,sizeof(dist)); q.push(x); inq[x]=true; dist[x]=0; while (!q.empty()) { int now=q.front(); q.pop(); for (int i=1;i<=m;i++)//枚举按哪个开关 { int k=now; for (int j=0;j

`——羌笛何须怨杨柳，春风不度玉门关 斯拉夫音乐实在是迷人，柴一这三个乐章，色彩各有不同，但都是百听不厌啊··· 今天又回味了帕格尼尼的钟 自打柴一在我脑子里阴魂不散后很久没循过帕格尼尼了 但还是那么具有魔性··· 今天为了打断绕脑袋三日的渔光曲= =听了拉赫 然而拉赫家钢协竟然都是小调  实在惊讶`