[隐式图搜索]UVa658

[隐式图搜索]UVa658

好题啊，好题就做了一个下午！

首先说此题是个状态转移的隐式图

然后判断位数是否符合的时候可以用到位运算符。

|运算只要有一个为1即为1

&两个都为1则为1

①判定某些位置是否为1，如判定2、4位置为1，则转化为判断x|0101是否等于x。

②判定某些位置是否为0，如判定2、4位置为0，则转化为判断x&1010是否等于x。

③将某些位置转化为1，如2、4位置转化为1，则令x=x|0101。

④将某些位置转化为0，如2、4位置转化为0，则令x=x&1010。

在用二进制表示状态的基础上采用这些位运算技巧之后，速度就变得比较快了。

然后是用的SPFA算法，队列是自己写的，比较快

至于SPFA算法中front_>MAX front=0 和 rear_>MAX rear=0

没懂什么意思，去掉也AC，有懂的麻烦留言解释一下

#includeusing namespace std;#define INF 0x7f7f7f7fint n,m;int w[110];char a[25],b[25];int s[2][110],t[2][110];int d[1<<25],inq[1<<25],q[1<<25];int init(){ scanf("%d%d",&n,&m); if(!n&&!m) return 0; memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); for(int i=0;iMAX) front_=0; inq[u]=0; for(i=0;i MAX) rear_=0; inq[v]=1; } } } } } if(d[0] == INF) printf("Bugs cannot be fixed.\n"); else printf("Fastest sequence takes %d seconds.\n", d[0]);}int main(){ int kase=0; while(init()){ printf("Product %d\n",++kase); SPFA(); printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。