软件补丁问题(SPFA+位运算)

枫林晚

2018-03-04 10:25:47

Solution

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; } ``` 总结:位运算一定要自己手动考虑,谁都可以看懂,但是有时候不容易想。