好题啊，好题就做了一个下午！ 首先说此题是个状态转移的隐式图 然后判断位数是否符合的时候可以用到位运算符。 |运算只要有一个为1即为1 两个都为1则为1 ①判定某些位置是否为
好题啊，好题就做了一个下午！
首先说此题是个状态转移的隐式图
然后判断位数是否符合的时候可以用到位运算符。
|运算只要有一个为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，有懂的麻烦留言解释一下
#include<bits/stdc++.h>using namespace std;
#define INF 0x7f7f7f7f
int 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;i<m;i++){
scanf("%d%s%s",&w[i],a,b);
for(int j=0;j<n;j++){
if(a[j]=='+') s[1][i]+=(1<<j);
if(a[j]!='-') s[0][i]+=(1<<j);
if(b[j]=='+') t[1][i]+=(1<<j);
if(b[j]!='-') t[0][i]+=(1<<j);
}
}
// for(int i=0;i<n;i++) printf("%d ",s[0][i]);
//7 3 1
return 1;
}
void SPFA(){
int u,v;
int MAX=(1<<n);
int i;
for(i=0;i<MAX;i++){
d[i]=INF;
inq[i]=0;
}
int front_=0,rear_=0;
d[MAX-1]=0;
q[rear_++]=MAX-1;//q[0]=7;
while(front_!=rear_){
u=q[front_++];
// printf("状态： %d\n",u);
// if(front_>MAX) front_=0;
inq[u]=0;
for(i=0;i<m;i++){
// printf("%d %d\n",s[1][i],s[0][i]);
if( (u|s[1][i])==u && (u&s[0][i])==u )
{
v=u;
v|=t[1][i];
v&=t[0][i];
if(d[u]+w[i]<d[v]){
d[v]=d[u]+w[i];
if(!inq[v]){
q[rear_++] =v;
// if(rear_ > 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;
}