对跳舞链(Dancing Links)和精确覆盖(DLX)的理解运用

精确覆盖问题

$n$ 行 $m$ 列 $01$ 矩形,从中选择若干行使得每一列有且恰好只有一个 $1$
hihocoder-1317
主要注意双向十字循环链表写法,$remove$和$resotre$互逆,DFS写法
这里的链表插入方法只适合跳舞链
remove时只改变上下信息,左右信息不改变
$remove(c)$:删除c列的所有行
DFS流程细节理解
第一次$remove$时已将所有可选行删除,之后调用$remove(c)$对所有可选行无影响

#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 1000
#define INF 0x3f3f3f3f
struct Node{
    int L,R,U,D,row,col;
}node[MAXN*MAXN+5];
int n,m,ncnt,Head,Cnt[MAXN+5];
void Init(){
    ncnt=-1,Head=0,memset(Cnt,0,sizeof(Cnt));for(int i=0;i<=m;i++)++ncnt,node[i].L=i-1,node[i].R=i+1,node[i].U=i,node[i].D=i;node[0].L=m,node[m].R=0;return ;
}
void Addnode(int i,int j,int st,int ed){
    ++ncnt,node[ncnt]=(Node){
    ed,st,node[j].U,j,i,j},Cnt[j]++;node[st].L=node[ed].R=ncnt;node[node[j].U].D=ncnt,node[j].U=ncnt;return ;
}
void Remove(int c){
    //删除第c列有节点的所有行的上下信息node[node[c].L].R=node[c].R;node[node[c].R].L=node[c].L;for(int i=node[c].D;i!=c;i=node[i].D)for(int j=node[i].R;j!=i;j=node[j].R){
    node[node[j].U].D=node[j].D;node[node[j].D].U=node[j].U;Cnt[node[j].col]--;}return ;
}
void Restore(int c){
    node[node[c].L].R=c;node[node[c].R].L=c;for(int i=node[c].U;i!=c;i=node[i].U)for(int j=node[i].L;j!=i;j=node[j].L){
    node[node[j].U].D=j;node[node[j].D].U=j;Cnt[node[j].col]++;}return ;
}
int order[MAXN+5];
bool DFS(int d){
    if(node[Head].R==Head)return 1;int Min=INF,c;for(int j=node[Head].R;j!=Head;j=node[j].R)if(Cnt[j]<Min)//可行解剪枝Min=Cnt[j],c=j;Remove(c);for(int i=node[c].D;i!=c;i=node[i].D){
    order[d]=node[i].row;for(int j=node[i].R;j!=i;j=node[j].R)Remove(node[j].col);if(DFS(d+1))return 1;for(int j=node[i].L;j!=i;j=node[j].L)Restore(node[j].col);}Restore(c);return 0;
}
int main(){
    int T=read();while(T--){
    n=read(),m=read();Init();for(int i=1;i<=n;i++){
    int st=ncnt+1,ed=ncnt+1;for(int j=1;j<=m;j++){
    int opt=read();if(!opt) continue;Addnode(i,j,st,ed),ed=ncnt;}}for(int j=1;j<=m;j++)if(Cnt[j]==0){
    puts("No");goto Break;}puts(DFS(1)==true?"Yes":"No");Break:;}return 0;
}

问题运用

可以抽象为选择第 $i$ 行是 选择某元素或某决策,列是对选择的限制或理解为任务 即:
第 $j$ 列的 $1$ :对于任务 $j$ 通过选择行只有一行满足
所以该算法运用于各种填数游戏中

#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 1000
#define INF 0x3f3f3f3f
struct Node{
    int L,R,U,D,row,col;
}node[MAXN+5];
int ncnt,Head,Row,Cnt[MAXN+5];
void Init(int M){
    ncnt=-1,Head=0,memset(Cnt,0,sizeof(Cnt));for(int i=0;i<=M;i++)++ncnt,node[i].L=i-1,node[i].R=i+1,node[i].U=i,node[i].D=i;node[0].L=M,node[M].R=0;return ;
}
void Addnode(int i,int j,int st,int ed){
    ++ncnt,node[ncnt]=(Node){
    ed,st,node[j].U,j,i,j},Cnt[j]++;node[st].L=node[ed].R=ncnt;node[node[j].U].D=ncnt,node[j].U=ncnt;return ;
}
void Remove(int c){
    //删除第c列所有节点的左右信息for(int i=node[c].D;i!=c;i=node[i].D)node[node[i].L].R=node[i].R,node[node[i].R].L=node[i].L;return ;
}
void Restore(int c){
    for(int i=node[c].U;i!=c;i=node[i].U)node[node[i].L].R=i,node[node[i].R].L=i;return ;
}
bool visc[MAXN+5];
int ansd,order[MAXN+5];
int h(){
    //至少需要步数int ret=0;for(int c=node[Head].R;c!=Head;c=node[c].R)visc[c]=1;for(int c=node[Head].R;c!=Head;c=node[c].R)if(visc[c]){
    ret++;visc[c]=0;for(int i=node[c].D;i!=c;i=node[i].D)for(int j=node[i].R;j!=i;j=node[j].R)visc[node[j].col]=0;//printf("%d ",node[j].col);}return ret;
}
void DFS(int d){
    if(d+h()>=ansd)return ;if(node[Head].R==Head){
    ansd=d;return ;}int c=node[Head].R;for(int j=node[Head].R;j!=Head;j=node[j].R)if(Cnt[j]<Cnt[c])c=j;for(int i=node[c].D;i!=c;i=node[i].D){
    order[d]=node[i].row;Remove(i);for(int j=node[i].R;j!=i;j=node[j].R)Remove(j);DFS(d+1);for(int j=node[i].L;j!=i;j=node[j].L)Restore(j);Restore(i);}return ;
}
int n,m,a[20][20];
int Id(int x,int y){
    return (x-1)*m+y;}
int main(){
    while(~scanf("%d %d",&n,&m)){
    int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    a[i][j]=read();if(a[i][j])a[i][j]=++cnt;}Init(cnt);int n1=read(),m1=read();ansd=INF,Row=0;for(int i=1;i<=n-n1+1;i++)for(int j=1;j<=m-m1+1;j++){
    Row++;int st=ncnt+1,ed=ncnt+1;for(int x=i;x<=i+n1-1;x++)for(int y=j;y<=j+m1-1;y++)if(a[x][y])Addnode(Row,a[x][y],st,ed),ed=ncnt;}DFS(0);printf("%d\n",ansd);}return 0;
}