题目描述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
你只要输出用的最少的药剂数就可以了，其实还有可能用尽了所有的药也不能将所有病治愈，那样的话你们只要输出“Thepatientwillbedead.”就可以了。
样例输入Sample Input
3
2
101
-110
样例输出Sample Output
2
数据范围及提示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#includeusing 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
——羌笛何须怨杨柳，春风不度玉门关 斯拉夫音乐实在是迷人，柴一这三个乐章，色彩各有不同，但都是百听不厌啊··· 今天又回味了帕格尼尼的钟 自打柴一在我脑子里阴魂不散后很久没循过帕格尼尼了 但还是那么具有魔性··· 今天为了打断绕脑袋三日的渔光曲= =听了拉赫 然而拉赫家钢协竟然都是小调 实在惊讶
