二进制储存状态+spfa
#include#include #include using namespace std;int b1[102],b2[102],f1[101],f2[102];int cost[102];char in[102];queue q;bool inque[1048577];int dis[1048577];int main(){ cin.sync_with_stdio(false); int n,m; cin>>n>>m; if(n==0) { //printf("0"); cout<<"0"; return 0; } int base,len; for(int i=1;i<=m;i++) { cin>>cost[i]; base=1; cin>>in; for(int j=0;in[j]!='\0';j++) { switch(in[j]) { case '+':b1[i]+=base;break; case '-':b2[i]+=base;break; case '0':break; } base*=2; } base=1; cin>>in; for(int j=0;in[j]!='\0';j++) { switch(in[j]) { case '-':f1[i]+=base;break; case '+':f2[i]+=base;break; case '0':break; } base*=2; } } base=1; int begin=0; for(int i=1;i<=n;i++) { begin+=base; base*=2; } for(int i=0;i<=begin;i++) dis[i]=0x7ffffff; q.push(begin); dis[begin]=0; inque[begin]=true; int pass,nxt; while(!q.empty()) { pass=q.front(); q.pop(); inque[pass]=false; for(int i=1;i<=m;i++) { if((pass&b1[i])!=b1[i]) continue; if((pass&b2[i])!=0) continue; int ha=pass&f1[i]; nxt=pass-ha; nxt=nxt|f2[i]; if(dis[nxt]