hdu 1818 It's not a Bug, It's a Feature!(位运算+bfs优先队列)

题意：给一个长度为n的bug，和m个补丁，然后是m个补丁的描述。第一个数字是这个补丁消耗的时间。

第1个字符串是这个补丁要工作需要满足的条件，第2个字符串是这个补丁的作用

详细一点说，

对于第一个字符串，假设是 -0-+0。 -号代表这个位的bug不能出现，也就是不能有3号和5号bug。(定义最右边为1号，为了到时候方便位运算) +号就是指这个位bug一定要出现，也就是一定要有2号bug。0就是指……没什么意思。

满足上述条件该补丁才能起作用。

对于第二个字符串，假设是00--+，-号代表这个补丁能杀掉这个位的bug，也就是杀掉2,3号。+号代表这个补丁会带来这个位的bug，也就是会新产生一个1号bug。

（假设bug长度为n，那么起始的时候，是1-n位都有bug，我们可以用一个二进制1111...1来表示）

解法：扩展状态的时候可以用位运算，容易理解又加快时间，具体的是&,|,~什么的，就请读者自己分析下吧（提示：不能出现的，必须出现的，能杀掉的，新产生的，4者单独储存）

题意理解后，很容易发现是一个单次消耗值不同的宽搜，对于这种题目，不像迷宫题，每次消耗值都是固定的。这种消耗值不固定的题目，一般都要使用优先队列，将当前消耗值最低的先出列扩展。而且，当扩展的时候找到最终答案时，也不能立即返回，因为即使是优先队列，也不能保证最后那个值是最低的。

举个例子 队列里

A-----B-----C 队头

现在C的值最低，由它扩展，假设C可以直接扩展到答案，那么它的消耗值就是 C+X，如果此时return，就可能丢失掉最优解。

因为，如果B出列，B也可以直接扩展到答案，那么它的消耗值是 B+Y，根据优先队列，C<B，但我们不能保证X<Y，所以有可能B+Y<C+X。

对于这种情况，我们只有在队列出队时判断它是不是答案，如果是，此时的答案肯定是最优解。

这种类型的题目还有一个要注意的就是标记数组的问题，绝对不能简单的对某个状态做标记，因为当我再次扩展到这个状态时，如果消耗值比以前的这个值小，我还是要更新它，并且加入队列，所以此时的vis就不是简单的一个0、1bool型了，还要负责记录消耗值。

类似的题目还有昨天做到的poj 2049，不过poj的这道题貌似数据又水了，不用那种判断也能过。

200ms飘过

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int vis[1100000];
struct node
{
    int noa,yesa;
    int time;
    int ka,ta;
}pat[105];
struct node2
{
   int bug;
   int time;
   bool operator <(const node2 &a) const
   {
       return time>a.time;
   }
};
int n,m;
bool isok(int k,int bug)
{
	if((pat[k].noa&bug)!=0) return false;
	if((pat[k].yesa&bug)!=pat[k].yesa) return false;
	return true;
}
int fix(int k,int bug)
{
    int tmp=bug;
    bug=((~pat[k].ka)&bug);
    bug=(pat[k].ta|bug);
    if(tmp==bug) return -1;
    return bug;
}
void bfs(int bug)
{
    priority_queue<node2> q;
    node2 tmp,tt;
    tmp.bug=bug;tmp.time=0;
    q.push(tmp);
    int mins=-1;
    while(!q.empty())
    {
        tmp=q.top();q.pop();
        if(tmp.bug==0)
        {
            mins=tmp.time;
            break;
        }
        for(int i=1;i<=m;i++)
        {
            tt=tmp;
            if(isok(i,tt.bug)) //第i种补丁应用到当前bug上
            {
                tt.bug=fix(i,tmp.bug);
                if(tt.bug<0) continue;
                tt.time+=pat[i].time;
                if(vis[tt.bug]!=-1&&tt.time>=vis[tt.bug]) continue;      //判断新旧时间，依此决定是否进入队列
                vis[tt.bug]=tt.time;
                q.push(tt);
            }
        }
    }
    if(mins==-1)
    {
        printf("Bugs cannot be fixed.\n");
    }
    else
    {
        printf("Fastest sequence takes %d seconds.\n",mins);
    }
}
int main()
{
    int bug;
    char a[200],b[200];
    int cas=1;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        bug=0;
        memset(pat,0,sizeof(pat));
        memset(vis,-1,sizeof(int)*(1<<n));
        bug=(1<<n)-1;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %s %s",&pat[i].time,a,b);
            for(int k=0;k<n;k++)
            {
                if(a[k]=='-')
                {
                    pat[i].noa+=(1<<(n-k-1));
                }
                else if(a[k]=='+')
                {
                    pat[i].yesa+=(1<<(n-k-1));
                }
            }
            for(int k=0;k<n;k++)
            {
                if(b[k]=='-')
                {
                    pat[i].ka+=(1<<(n-k-1));
                }
                else if(b[k]=='+')
                {
                    pat[i].ta+=(1<<(n-k-1));
                }
            }
        }
        printf("Product %d\n",cas++);
        bfs(bug);
        putchar(10);
    }
    return 0;
}