P2761 软件补丁问题

状态压缩+dij 最短路

---

考虑建图，由于 (n,m) 较小，所以可以把所有当前含有的错误用二进制的形式压在一个 int 里
然后把这个数当作我们图中的节点

其实建图的时候不用真正的连边，在跑 dij 的时候枚举每一个补丁，按照题意判断它能不能用，再计算出使用完后的错误集合，也就是一条边的终点
用一点简单的位运算就可以了

然后这个题还混入了网络瘤24题？

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int n,m;
int timee[106];
int f1[106],f2[105],b1[106],b2[106];
int dis[1050005],heap[1050005],size;
int in[1050005];
inline void push(int x){
	heap[++size]=x;
	reg int i=size,fa;
	while(i>1){
		fa=i>>1;
		if(dis[heap[fa]]<=dis[heap[i]]) return;
		std::swap(heap[fa],heap[i]);i=fa;
	}
}
inline int pop(){
	int ret=heap[1];heap[1]=heap[size--];
	int i=1,ls,rs;
	while((i<<1)<=size){
		ls=i<<1;rs=ls|1;
		if(rs<=size&&dis[heap[rs]]<dis[heap[ls]]) ls=rs;
		if(dis[heap[ls]]>=dis[heap[i]]) break;
		std::swap(heap[i],heap[ls]);i=ls;
	}
	return ret;
}
inline void get(int &x,int &y){
	reg int i=0;
	reg char c=std::getchar();
	while(c!='0'&&c!='+'&&c!='-') c=std::getchar();
	while(1){
		i++;
		if(c=='0');
		else if(c=='+') x|=1<<(i-1);
		else if(c=='-') y|=1<<(i-1);
		else break;
		c=std::getchar();
	}
}
inline void dij(int s){
	std::memset(dis,0x3f,sizeof dis);dis[s]=0;
	push(s);in[s]=1;
	reg int u,v;
	while(size){
		u=pop();in[u]=0;
		for(reg int i=1;i<=m;i++)if(((u&b1[i])==b1[i])&&!(u&b2[i])){
			v=(u&(~f1[i]))|f2[i];
			if(dis[v]>dis[u]+timee[i]){
				dis[v]=dis[u]+timee[i];
				if(!in[v]) push(v),in[v]=1;
			}
		}
//		else std::printf("no! u=%d id=%d , for b1 : %d , for b2 : %d
",u,i,((u&b1[i])==b1[i]),!(u&b2[i]));
	}
}
int main(){
	n=read();m=read();
	for(reg int i=1;i<=m;i++){
		timee[i]=read();
		get(b1[i],b2[i]);get(f2[i],f1[i]);
	}
	dij((1<<n)-1);
	std::printf("%d",dis[0]==0x3f3f3f3f?0:dis[0]);
	return 0;
}