http://www.vijos.cn/Problem_Show.asp?id=1026
描述 Description
羽毛笔和im是抽签到同一个考场的，她们突然闻到一阵刺鼻的化学试剂的气味。机灵鼠：(头都不抬)你们是考生么?还在门口磨蹭什么?快进来帮我忙!!……怎么还不进来?你们拖赛，拖赛，把你们的青春都拖掉赛……
im：开…开策了>_<
羽毛笔：哎呀~~机灵鼠大人要我们帮什么忙?^^
机灵鼠：你们看这里的这些药，都是我研制的对付各种症状的解药。可是我一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症……(im：那…那是解药还是毒药啊?)……经过我天才的努力(背景：我是天才！！)，终于弄清了每种药的具体性能(路人甲：那是你自己配的吗？-_-)，我会把每种药能治的病症和能使人患上的病症列一张清单给你们，然后你们要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声，病症的数目不超过10种(小呆：偶是好人吧^^)，我的药是用不完的，就是说每种药剂都可以被重复使用。给你们的单子里第一行是病症的总数n，第二行是药剂的种类m(0<m<=100)，以下有m行，每行有n个数字用空格隔开，文件的第i+2行的n个数字中，如果第j 个数为1，就表示第i种药可以治愈病症j(如果患有这种病的话则治愈，没有这种病则无影响)，如果为0表示无影响，如果为-1表示反而能使人得上这种病(无病患上，有病无影响)。我制的药任何两种性能都不同。你们只要给我用的最少的药剂数就可以了。无解输出：“The patient will be dead.”
给你们个样例：
样例输入 Sample Input
3
2
1 0 1
-1 1 0
样例输出 Sample Output
2
时间限制 Time Limitation
各个测试点1s
注释 Hint
其实还有可能用尽了所有的药也不能将所有病治愈(真是不好意思嗬^^bb).im：做不出来啊~~哇啊啊啊~~(暴走中)羽毛笔：哎呀~~im……来来吃药了。^^
来源 Source
Vivian Snow
From 正·蠢盟演义——战略版 Fools-League Tactics
分析：
以人是否健康为状态(0 or 1),则状态数最大为2^10种,再BFS,并且将二进制转换为十进制利用hash判重,找到解即可输出。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
struct node
{
int dep;
int b[11];
} list[1025];
int F[11];
bool hash[1025];
int a[1025][11];
int n,m;
int main()
{
F[1]=1;
for (int i=2;i<=10;i++) F[i]=F[i-1]*2;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
int xx,tt,head,tail;
xx=0;
for (int i=1;i<=n;i++) xx+=F[i];
memset(hash,false,sizeof(hash));
memset(list,0,sizeof(list));
head=tail=1;
while (head<=tail)
{
for (int i=1;i<=m;i++)
{
tail++;
tt=0;
for (int j=1;j<=n;j++)
{
if (a[i][j]==1) list[tail].b[j]=1;
if (a[i][j]==0) list[tail].b[j]=list[head].b[j];
if (a[i][j]==-1) list[tail].b[j]=0;
if (list[tail].b[j]==1) tt+=F[j];
}
if (!hash[tt])
{
hash[tt]=true;
list[tail].dep=list[head].dep+1;
if (tt==xx)
{
printf("%d\n",list[tail].dep);
return 0;
}
}
else tail--;
}
head++;
}
printf("The patient will be dead.\n");
return 0;
}