@[toc]
添加链接描述
题目描述
T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m
个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件包含 B1[i]中的所有错误，而不包含
B2[i]中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误
F2[i]。另外，每个补丁都耗费一定的时间。试设计一个算法，利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 n 个错误和 m
个补丁程序，找到总耗时最少的软件修复方案。
输入格式
第 1 行有 2 个正整数 n 和 m，n 表示错误总数，m表示补丁总数，1<=n<=20, 1<=m<=100。
接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数，表示运行补丁程序 i 所需时间，以及 2 个长度为 n
的字符串，中间用一个空格符隔开。第 1 个字符串中，如果第 k 个字符 bk 为“+”，则表示第 k 个错误属于 B1[i]，若为“-”，则表示第 k 个错误属于
B21[i]，若为“0”，则第 k 个错误既不属于 B1[i]也不属于 B2[i]，即软件中是否包含第 k 个错误并不影响补丁 i
的可用性。第 2 个字符串中，如果第 k 个字符 bk为“-”，则表示第 k 个错误属于 F1[i]，若为“+”，则表示第 k 个错误属于
F2[i]，若为“0”，则第 k 个错误既不属于 F1[i]也不属于 F2[i]，即软件中是否包含第 k 个错误不会因使用补丁i 而改变。
输出格式
程序运行结束时，将总耗时数输出。如果问题无解，则输出 0。
输入输出样例
输入
3 3 1 000 00- 1 00- 0-+ 2 0-- -++
输出
8
题解：
样例分析：
圆圈表示还没修复，三角表示已修复
按照题目所给要求以及样例读入，我们可以得到以下分析
所采用的补丁分别为补丁1,2，1,3，1,2，1.
然后错误全部修复，总耗时为8
思路：
我是在刷网络流24题遇到的，看完后怎么想也想不到网络流。。。
感觉dp或者是最短路？
看了题解还真是，妙啊 ~ ~ （啥玩意还带这么坑人的）
还真是网络流24题中没网络流，老婆饼里没老婆借用一张照片
第一步： 怎么和最短路联系到一起？
最短路无疑就是起点，终点，中间点，还有各点之间的线段
前三种点都是节点，在本题中节点就是错误修复的状态，起点就是全没修复，终点就是全修复了，每次修复一些错误或者新添一些错误，此时的修复状态就是当前状态。线段长度就是运行补丁的时间。我们在输入每一个补丁的时候，可以枚举一种状态，如果当前状态可以使用补丁，就算出使用补丁后的状态，前状态连一条边到后状态，长度也就是补丁时长
第二步： 状态压缩
n<=20，也就是最多20个错误，而每个错误只有修好和没修好俩状态，我们可以用01来表示（1表示没修好，0表示修好），这样20个错误其实就是一个01串，
比如bug3已经修好，1和2还未修好，那01串就是110，转化成十进制就是6。而初始状态（都未修好）为111，对应7。结束状态是都修好了为000，对应0。当有n个错误时，初始状态就是n个1，十进制也就是2^n^-1，即（1<<n）-1。结束就是0
第三步： 状态转移
补丁使用是有严格要求的，有些位置为1，有些位置为0，才能使用
题目中有b1，b2，f1，f2
软件包含b1错误，不包含b2错误，能够修复f1，加入错误f2
我们看看补丁3
0-- -++
使用状态：（判断一个补丁包能否使用）
b1是000=0（因为第一个字符串里面没有+）
b2是011=3（第一个字符串中 第二三位是-）
记当前状态为x
1.判断x中b1位上是否都为1（说明x是否含有b1错误）
我们可以将x与b1按位与。如果得到的值是b1本身，那就说明x的b1位上都是1
2.判断x中b2位上是否都为0（说明x是否含有b2错误）
也是将b2与x按位与，如果得到的都是0，说明x的b2位上都是0
if((x&p[i].b1)==p[i].b1 && (x&p[i].b2)==0)//说明该补丁包可以使用
修复状态：（使用后的情况）
使用后，f1位置会修好变成0，f2会变成1。
当前状态为x，如果要将f2位置变成1，直接x或上f2即可。f1位置变成0，我们可以或上一个f1，使得当前状态的所有f1位置都变成1，再异或一个f1，这样就可以将f1所有位置变成0.
int y=((x|p[i].f1)|p[i].f2)^p[i].f1;
应该算讲的很详细了吧!
代码：
//第一个字符串中+
//第二个字符串-
#include<bits/stdc++.h>
#define Maxn 100
#define Maxm 100
#define Maxnum 4000000
using namespace std;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n,m;
int ST;
struct debug{
int b1;
int b2;
int f1;
int f2;
int T;
}hero[Maxm+2];
priority_queue < pair<int,int> > q;
int dist[Maxnum];
int vis[Maxnum];
void dj(){
memset(dist,0x3f,sizeof(dist));
dist[ST]=0;
q.push(make_pair(0,ST));
while(!q.empty()){
int now=q.top().second;
q.pop();
if(vis[now]==1) continue;
vis[now]=1;
for(int i=1;i<=m;i++){
if( (hero[i].b1&now)==hero[i].b1 && (hero[i].b2&now)==0 ){
int v=((now|hero[i].f1)^hero[i].f1)|hero[i].f2;
if(dist[now]+hero[i].T<dist[v]){
dist[v]=dist[now]+hero[i].T;
q.push(make_pair(-dist[v],v));
}
}
}
}
}
int main(){
n=read(); m=read();
for(int i=1;i<=n;i++)
ST=ST|(1<<i);//ST表
cout<<ST<<endl;
for(int i=1;i<=m;i++){
hero[i].T=read();
string B,F;
cin>>B>>F;
for(int j=0;j<=n-1;j++){
if(B[j]=='+')
hero[i].b1=hero[i].b1|(1<<(j+1));
if(B[j]=='-')
hero[i].b2=hero[i].b2|(1<<(j+1));
if(F[j]=='+')
hero[i].f2=hero[i].f2|(1<<(j+1));
if(F[j]=='-')
hero[i].f1=hero[i].f1|(1<<(j+1));
}
}
dj();
if(dist[0]==dist[Maxnum-1])
cout<<"0";
else
cout<<dist[0];
return 0;
} 
京公网安备 11010502036488号