软件补丁问题(SPFA+位运算)
枫林晚
2018-03-04 10:25:47
2018年3月4日10:26:33
洛谷P2761
1.考虑到所有的错误只有“修复,未修复”两种情况,所以可以用0,1标记压缩状态,采用位运算减少时空浪费。
又考虑到有修复时间的关系,将时间抽象成边,将状态抽象为点(设修复为0,未修复为1)最后从(1<<n)-1开始寻找到0的最短路,SPFA一边建图一边松弛即可。
2.实现过程中,难点在于对二进制表示,以及位运算组合判断的处理。
首先,状态要表示(见前);
其次,补丁b,f要表示。
最初考虑用两个数来表示b,f,发现受“不动错误”影响,无法转移运算。故采用四个数记录,b+,b-,f+,f-。再推倒出位运算判断方式,以及转移方式即可。
最终位运算方式:
判断:b+:(原状态~)&bp为0可以通过
b-:&为0可以通过
转移(更新)f+:|
f-:(fj取反)&原状态
另:b+b-f+f-定义比较繁琐,利用草稿纸码上条件思路比较省事。
附代码:
```c
#include<bits/stdc++.h>
using namespace std;
int n,m;
int hd=1,tl=0;
int q[1050000];
bool vis[1050000];
int dis[1050000];
struct repair{
int t;
int bp,bj,fp,fj;
}bu[111];
int main()
{
char kk[23];
char h;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d ",&bu[i].t);
for(int j=1;j<=n;j++)
{
h=getchar();
if(h=='+') bu[i].bp+=1<<(n-j);
if(h=='-') bu[i].bj+=1<<(n-j);
}
h=getchar();
for(int j=1;j<=n;j++)
{
h=getchar();
if(h=='+') bu[i].fp+=1<<(n-j);
if(h=='-') bu[i].fj+=1<<(n-j);
}
}
//for(int i=1;i<=m;i++)
//cout<<bu[i].t<<" "<<bu[i].bp<<" "<<bu[i].bj<<" "<<bu[i].fp<<" "<<bu[i].fj<<endl;
//cout<<endl;
q[++tl]=(1<<n)-1;
memset(dis,0x3f3f3f3f,sizeof dis);
dis[(1<<n)-1]=0;
while(hd<=tl)
{
int zhuang=q[hd];hd++;vis[zhuang]=0;
//cout<<zhuang<<" "<<dis[zhuang]<<endl;
for(int i=1;i<=m;i++)
{
if(((~zhuang)&bu[i].bp)!=0) continue;
if((zhuang&bu[i].bj)!=0) continue;
//cout<<"panduan "<<i<<" && "<<zhuang<<" == "<<(zhuang&bu[i].bj)<<endl;
int tt=(zhuang|bu[i].fp);
tt=(tt&(~bu[i].fj));
if(dis[tt]>dis[zhuang]+bu[i].t)
{
dis[tt]=dis[zhuang]+bu[i].t;
//cout<<"gengxin "<<i<<" -> "<<tt<<" "<<dis[tt]<<endl;
if(!vis[tt])
{
vis[tt]=1;
q[++tl]=tt;
}
}
}
}
if(dis[0]==0x3f3f3f3f) printf("0");
else printf("%d",dis[0]);
return 0;
}
```
总结:位运算一定要自己手动考虑,谁都可以看懂,但是有时候不容易想。