题目连接（vj）：https://vjudge.net/problem/UVA-658
题意：补丁在修正 bug 时，有时也会引入新的 bug。假定有 n（n≤20）个潜在 bug 和 m（m≤100） 个补丁，每个补丁用两个长度为 n 的字符串表示，其中字符串的每个位置表示一个 bug。第一 个串表示打补丁之前的状态（“-” 表示该 bug 必须不存在，“+” 表示必须存在，0 表示无所 谓），第二个串表示打补丁之后的状态（“-” 表示不存在，“+” 表示存在，0 表示不变）。每 个补丁都有一个执行时间，你的任务是用最少的时间把一个所有 bug 都存在的软件通过打补 丁的方式变得没有 bug。一个补丁可以打多次。 在任意时刻，每个 bug 可能存在也可能不存在，所以可以用一个 n 位二进制串表示当前软 件的 “状态”。打完补丁之后，bug 状态会发生改变，对应 “状态转移”。是不是很像动态规 划？可惜动态规划是行不通的，因为状态经过多次转移之后可能会回到以前的状态，即状态 图并不是 DAG。如果直接用记忆化搜索，会出现无限递归。 正确的方法是把状态看成结点，状态转移看成边，转化成图论中的最短路径问题，然后 使用 Dijkstra 或 Bellman-Ford 算法求解。不过这道题和普通的最短路径问题不一样：结点很 多，多达 2 n 个，而且很多状态根本遇不到（即不管怎么打补丁，也不可能打成那个状态）， 所以没有必要像前面那样先把图储存好。 还记得第 7 章中介绍的 “隐式图搜索” 吗？这里也可以用相同的方法：当需要得到某个结 点 u 出发的所有边时，不是去读 G[u]，而是直接枚举所有 m 个补丁，看看是否能打得上。不管 是 Dijsktra 算法还是 Bellman-Ford 算法，这个方法都适用。本题很经典，强烈建议读者编程实现。
以上题意以及思路来自紫书
解题思路：抽象成最短路问题，因为状态（节点）太多，而且很多不会出现，所以不能单独建完图再跑最短路，所以采用隐式图，每次扩展遍历一遍已知补丁，匹配成功则看是否可以松弛，记录松弛后的状态。
当前状态唯一确定，所以压缩为一个n位二进制串，0表示无bug，1表示有，而补丁的状态不唯一确定，所以用两个二进制串表示，has串和no串，has串1表示该位置一定有，no串1表示该位置一定无。
匹配方法：cur表示当前状态。如果 cur&no==0并且cur|yes=cur 则匹配成功，匹配成功后松弛后的状态为 v=(u|p.to_has)&(~p.to_no)。然后跑dijkstra即可。
代码如下：
#include<bits/stdc++.h>
#define MAX (1<<20)+10
#define INF 0x3fffffff
using namespace std;
struct data
{
int from_no,from_has,to_no,to_has,dist;
} patch[];
struct heapnode
{
int d,u;
bool operator < (const heapnode& rhs) const
{
return d>rhs.d;
}
};
int l,m;
bool vis[MAX];
long long d[MAX];
void init(void)
{
; i<m; i++)
{
patch[i].from_has=;
patch[i].from_no=;
patch[i].to_has=;
patch[i].to_no=;
}
memset(vis,,sizeof(vis));
; i<MAX; i++)
d[i]=INF;
}
bool dijkstra(void)
{
priority_queue<heapnode> Q;
<<l)-;
d[s]=;;
Q.push((heapnode){,s});
while(!Q.empty())
{
heapnode x=Q.top();
Q.pop();
int u=x.u;
if(vis[u]) continue;
vis[u]=;
; i<m; i++)
{
data &p=patch[i];
if(!(u&p.from_no)&&((u|p.from_has)==u))//匹配成功
{
int v=(u|p.to_has)&(~p.to_no);
if(d[v]>d[u]+p.dist)
{
d[v]=d[u]+p.dist;
Q.push((heapnode){d[v],v});
}
}
}
}
]==INF)
;
;
}
int main()
{
;
while(~scanf("%d%d",&l,&m)&&l)
{
init();
; i<m; i++)
{
],to[];
int dis;
scanf("%d%s%s",&dis,from,to);
patch[i].dist=dis;
; j<l; j++)
{
<<j);
<<j);
<<j);
<<j);
}
}
printf("Product %d\n",++T);
if(dijkstra())
printf(]);
else
printf("Bugs cannot be fixed.\n");
printf("\n");
}
}