昨天和前天学习了DLX,在解决一类搜索问题(精确覆盖和重复覆盖)时具有很好的效果。
精确覆盖的定义:给定一个01矩阵,要求从中选出一些行,使得每列有且只有有一个一;
重复覆盖的定义:给定一个01矩阵,要求从中选出一些列,使得每列至少有一个一。
模板:(参考rabbit的模板)
struct DLX { int L[maxn],R[maxn],U[maxn],D[maxn]; int row[maxn],col[maxn]; int ans[maxm],S[maxm],H[maxm]; bool vis[maxn]; int cnt,size; /*common part */ void ini(int m) { for(int i=0; i<=m; i++) { S[i]=0; L[i]=i-1; R[i]=i+1; U[i]=D[i]=i; } memset(H,-1,sizeof(H)); R[m]=0; L[0]=m; size=m+1; } void add(int x,int y) { // cout<<x<<' '<<y<<endl; S[col[size]=y]++; row[size]=x; D[size]=D[y]; U[D[y]]=size; U[size]=y; D[y]=size; if(H[x]<0) { H[x]=L[size]=R[size]=size; } else { R[size]=R[H[x]]; L[R[H[x]]]=size; L[size]=H[x]; R[H[x]]=size; } size++; } /*exact cover*/ void Remove(int c) { L[R[c]]=L[c],R[L[c]]=R[c]; for(int i=D[c]; i!=c; i=D[i])for(int j=R[i]; j!=i; j=R[j]) U[D[j]]=U[j],D[U[j]]=D[j],S[col[j]]--; } void Resume(int c) { L[R[c]]=R[L[c]]=c; for(int i=U[c]; i!=c; i=U[i])for(int j=L[i]; j!=i; j=L[j]) ++S[col[D[U[j]]=U[D[j]]=j]]; } bool dance(int k) { int c; if((c=R[0])==0)return true; int tmp=inf; for(int i=R[0]; i; i=R[i])if(S[i]<tmp)tmp=S[i],c=i; Remove(c); for(int i=D[c]; i!=c; i=D[i]) { for(int j=R[i]; j!=i; j=R[j])Remove(col[j]); if(dance(k+1))return true; for(int j=L[i]; j!=i; j=L[j])Resume(col[j]); } Resume(c); return false; } /*repeat cover*/ void Remove2(int c) { for(int i=D[c]; i!=c; i=D[i]) L[R[i]]=L[i],R[L[i]]=R[i]; } void Resume2(int c) { for(int i=U[c]; i!=c; i=U[i]) L[R[i]]=R[L[i]]=i; } int Astar() { int res=0; for(int i=R[0]; i; i=R[i])vis[i]=false; for(int i=R[0]; i; i=R[i])if(!vis[i]) { res++,vis[i]=1; for(int j=D[i]; j!=i; j=D[j]) for(int k=R[j]; k!=j; k=R[k]) vis[col[k]]=1; } return res; } void dance2(int k,int &lim) { if(k+Astar()>=lim)return; if(R[0]==0) { if(lim>k)lim=k; return; } int c,tmp=inf; for(int i=R[0]; i!=0; i=R[i]) if(S[i]<tmp)tmp=S[i],c=i; for(int i=D[c]; i!=c; i=D[i]) { Remove2(i); for(int j=R[i]; j!=i; j=R[j])Remove2(j); dance2(k+1,lim); for(int j=L[i]; j!=i; j=L[j])Resume2(j); Resume2(i); } } } dlx;
一些题目:
精确覆盖模板题:
POJ 3740 Easy Finding
HUST 1017 Exact Cover
ZOJ 3209 Treasure Map
精确覆盖 建图+输出方案:
HDU 3663 Power Stations
重复覆盖模板题:
HDU 2119 Matrix
重复覆盖+建图+输出方案:
HDU 2828 Lamp
FZU 1686 神龙的难题
重复覆盖+二分:
HDU 2295 Radar (二分距离)
HDU 3656 Fire Station (二分距离坐标);