题解 P4929 【【模板】舞蹈链（DLX）】

Setsugesuka · 2018-10-23 15:05:01 · 题解

看到没有人写题解，蒟蒻我就想要来刷一发QWQ(很想过审核的说QAQ)

关于精确覆盖问题

首先，我们来考虑如下的一个问题：

　　给定一个 m 行，n 列的矩阵，矩阵中只有 0 或 1 两种数字。找到最少的行数，使得对于矩阵的每一列 j，在你挑选的这些行中，有且仅有一行的第 j 个元素为 1 。

　　(n,m) \leq 15

不难发现，对于\leq 15的数据，我们可以直接采用穷举法。对于每一行，都有取或不取两种操作，所以最大的操作数也只有 2 ^ 15 次，即使代码再丑，吸一口氧气也总归是能够过的。

　　那么当(n,m) \leq 50的时候呢？

这时候我们发现， 2 ^ 50 次肯定是会爆炸的，难道我们要用状态压缩DP来处理这道题吗？可以是可以，但是对于我这种菜的一批的蒟蒻来说，肯定是不行的(不会写状压QAQAQAQAQAQ.jpg)。那么，这个时候，我们考虑一些更加高级的搜索。

搜索与回溯

在初学OI的时候，相信大家都学过深度优先搜索，在深度优先搜索中，有一个很重要的思想就是回溯。那么，对于精确覆盖问题，我们能不能也采用这个策略呢？答案是可以的。让我们来看一看回溯的过程。

　　首先我们假设拥有以下一个矩阵：

　　　1　0　0　1

　　　0　1　0　0

　　　1　0　1　1

　　　0　0　1　0

显然，我们首先会选择第一行，然后选择第二行，再选择第三行，发现并不行，于是我们返回到选择第二行的时候，重新选择第四行，成功发现了答案。事实上，在小规模的数据上，与暴力并没有太大的差异。但是当数据很大的时候，回溯显然能更快地求出答案(但是时间复杂度完全是玄学)。由此，我们得到了一个实现 X 算法的思路。但是，我们思考刚刚描述的过程，我们选择前三行发现不行是因为我们发现了在一列上有了多个 1 。那么，我们能不能在找寻下一行的时候，就删除掉一些显然不会被选取行呢？答案是可行的。

X算法

我们用Markdown的表格来先生成一个矩阵。(QAQ蒟蒻我不会插图片,手写的又丑)

0	1	0	0	0	1	0
0	0	0	1	1	1	0
0	1	1	0	0	0	1
1	0	0	1	0	0	1
1	0	0	1	0	0	0
0	0	1	0	1	0	1

考虑如上的算法，首先，我们选取了第一行，在第一行中，第二列与第六列是 1 我们标记上第二列与第六列，然后对于这两列，从头往下算，找到这两列同样是 1 的行并删除它。在上图中，我们会删除掉第二第三行，得到一个 3 x 5的矩阵：

1	0	1	0	1
1	0	1	0	0
0	1	0	1	1

之后，我们选择第一行，按照如上规则，删去行后，发现矩阵空了，但是我们只得到了 5 个 1 。这显然是不对的，于是我们回溯一步，选择第二行，按照如上规则删除，最后会剩下 3 个 1 ，符合我们的题意。

以上的过程，就是 X 算法。

考虑存图方法

我们思考如何来储存这张图，如果直接用二维矩阵的话。删除操作和回溯操作都会用掉很大的空间和时间，这显然是十分不妥的。我们考虑上文写到的算法描述，快速删除一个元素，链表就能实现，那么如何实现回溯呢？其实很简单，我们在删除的时候，不删除这个点的空间，只是把这个点给“忽略”了。回溯的时候，只需要把与这个点相连的指针恢复回来就可以了。因此，我们在这里引入十字交叉双向循环链表。这种链表结构的每个结点有两类数据，分别为指针域和数据域。指针域为left、right、up、down，分别指向左、右、上、下四个其它结点，数据域则是这个结点对应于原始矩阵的行编号rowIdx，列编号colIdx。对于复杂的问题，数据域可能还会有更多的内容。

struct DLXnode{
    int r,c;
    DLXnode *U,*D,*L,*R;
};

那么，如何将一个矩阵变为一个十字交叉双向循环链表呢？在DLX中，我们引入额外节点来维护这个结构，它们分别是：

总表头head，将列与行串起来，实现更快的删除，插入等操作，同时为判断矩阵为空提供了便利。
列首数组col，维护每一列的元素。
行首节点row，维护每一行的元素。
元素节点node，也就是在这个矩阵中的普通节点。

在这里引用一下大佬的一篇博客，如果我的上述形容没有很好地让你听懂，你可以去看《跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题》这一篇文章，写的非常好，图解非常详细(特别是相对于我这个渣题解)。看了他的介绍可以让你更好地理解以下代码(我这个题解的唯一优势可能就在于我这个是C++了QAQ)。

那么，很显然，当我们得到行数和列数时，就可以直接初始化了

void init(int r,int c){
    cnt=0;
    head.r=r;
    head.c=c;
    head.L=head.R=head.U=head.D=&head;
    for(int i=0;i<c;i++){
        col[i].r=r;
        col[i].c=i;
        col[i].L=&head;
        col[i].R=head.R;
        col[i].L->R=col[i].R->L=&col[i];
        col[i].U=col[i].D=&col[i];
        sz[i]=0;
    }
    for(int i=r-1;i>-1;i--){
        row[i].r=i;
        row[i].c=c;
        row[i].U=&head;
        row[i].D=head.D;
        row[i].U->D=row[i].D->U=&row[i];
        row[i].L=row[i].R=&row[i];
    }
}

初始化之后，我们就要输入矩阵了。但在这之前，我们先观察一下问题，问题只要求我们使得 1 完全覆盖，和 0 没有任何关系。于是我们不难想到，在读入图时，我们只保存 1 的位置，然后更新node的值。

以下分别为插入和main函数读入代码：

 scanf("%d %d",&m,&n);
    init(m,n);
    int sr;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&sr);
            if(sr==1){
                addnode(i,j);
            }
        }
    }

inline void addnode(int r,int c){
    DLXnode *ptr=&node[cnt++];
    ptr->r=r;
    ptr->c=c;
    ptr->R=&row[r];
    ptr->L=row[r].L;
    ptr->L->R=ptr->R->L=ptr;
    ptr->U=&col[c];
    ptr->D=col[c].D;
    ptr->U->D=ptr->D->U=ptr;
    ++sz[c];
}

在完成了图的构建后，我们就可以让指针舞动起来了。

Let's dance！

首先，我们考虑如何对一个节点进行删除和回溯。如上文，我们并不用删除掉这个行的每个元素，我们只需要对行首，列首元素进行操作，让我们在搜索过程中忽略掉它们，就实现了删除操作了，同样的，这样做的好处在于回溯的时候不需要开辟新的内存空间，也就不会MLE(money溢出)。

inline void delLR(DLXnode *ptr){
    ptr->L->R=ptr->R;
    ptr->R->L=ptr->L;
}

inline void delUD(DLXnode *ptr){
    ptr->U->D=ptr->D;
    ptr->D->U=ptr->U;
}

inline void reLR(DLXnode *ptr){
    ptr->L->R=ptr->R->L=ptr;
}

inline void reUD(DLXnode *ptr){
    ptr->U->D=ptr->D->U=ptr;
}

同理，对于行列的删除与回溯操作，也很容易地就能写出来了。

inline void cover(int c){
    if(c==n){
        return;
    }
    delLR(&col[c]);
    DLXnode *R,*C;
    for(C=col[c].D;C!=(&col[c]);C=C->D){
        if(C->c==n){
            continue;
        }
        for(R=C->L;R!=C;R=R->L){
            if(R->c==n){
                continue;
            }
            --sz[R->c];
            delUD(R);
        }
        delLR(C);
    }
}

inline void re(int c){
    if(c==n){
        return;
    }
    DLXnode *R,*C;
    for(C=col[c].U;C!=(&col[c]);C=C->U){
        if(C->c==n){
            continue;
        }
        reLR(C);
        for(R=C->R;R!=C;R=R->R){
            if(R->c==n){
                continue;
            }
            ++sz[R->c];
            reUD(R);
        }
    }
    reLR(&col[c]);
}

在写出函数主体部分前，我们先重新思考一遍 X 算法

如果矩阵A没有列（即空矩阵），则当前记录的解为一个可行解；算法终止，成功返回；
否则选择矩阵A中“1”的个数最少的列c；（确定性选择）
a:如果存在A[r][c]=1的行r，将行r放入可行解列表，进入步骤4)；（非确定性选择）

b.如果不存在A[r][c]=1的行r，则剩下的矩阵不可能完成精确覆盖，说明之前的选择有错（或者根本就无解），需要回溯，并且恢复此次删除的行和列，然后跳到步骤3)a；

对于所有的满足A[r][j]=1的列j，对于所有满足A[i][j]=1的行i，将行i从矩阵A中删除；将列j从矩阵A中删除； 5. 在不断减少的矩阵A上递归重复调用上述算法；

(以上 X 算法的中文概述引自与博客夜深人静写算法（九）- Dancing Links X（跳舞链）该博客内容也十分优秀，如果读到这里也还没理解DLX的话强烈推荐去阅读这篇博客，但博主码风更偏向于工程风。)

那么，显然地，dance部分也就能写出来了。

bool dance(int k){
    if(head.L==(&head)){
        for(int i=0;i<k;i++){
            printf("%d ",ans[i]);
        }
        return true;
    }
    int INF=(1<<30),c=-1;
    for(DLXnode *ptr=head.L;ptr!=(&head);ptr=ptr->L){
        if(sz[ptr->c]<INF){
            INF=sz[ptr->c];
            c=ptr->c;
        }
    }
    cover(c);
    DLXnode *ptr;
    for(ptr=col[c].D;ptr!=(&col[c]);ptr=ptr->D){
        DLXnode *rc;
        ptr->R->L=ptr;
        for(rc=ptr->L;rc!=ptr;rc=rc->L){
            cover(rc->c);
        }
        ptr->R->L=ptr->L;
        ans[k]=ptr->r+1;
        if(dance(k+1)){
            return true;
        }
        ptr->L->R=ptr;
        for(rc=ptr->R;rc!=ptr;rc=rc->R){
            re(rc->c);
        }
        ptr->L->R=ptr->R;
    }
    re(c);
    return false;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int ans[MAXN];
struct DLXnode{
    int r,c;
    DLXnode *U,*D,*L,*R;
};
DLXnode node[MAXN*MAXN];
DLXnode row[MAXN];
DLXnode col[MAXN];
DLXnode head;
int cnt;
int sz[MAXN];
int n,m;

void init(int r,int c){
    cnt=0;
    head.r=r;
    head.c=c;
    head.L=head.R=head.U=head.D=&head;
    for(int i=0;i<c;i++){
        col[i].r=r;
        col[i].c=i;
        col[i].L=&head;
        col[i].R=head.R;
        col[i].L->R=col[i].R->L=&col[i];
        col[i].U=col[i].D=&col[i];
        sz[i]=0;
    }
    for(int i=r-1;i>-1;i--){
        row[i].r=i;
        row[i].c=c;
        row[i].U=&head;
        row[i].D=head.D;
        row[i].U->D=row[i].D->U=&row[i];
        row[i].L=row[i].R=&row[i];
    }
}

inline void addnode(int r,int c){
    DLXnode *ptr=&node[cnt++];
    ptr->r=r;
    ptr->c=c;
    ptr->R=&row[r];
    ptr->L=row[r].L;
    ptr->L->R=ptr->R->L=ptr;
    ptr->U=&col[c];
    ptr->D=col[c].D;
    ptr->U->D=ptr->D->U=ptr;
    ++sz[c];
}

inline void delLR(DLXnode *ptr){
    ptr->L->R=ptr->R;
    ptr->R->L=ptr->L;
}

inline void delUD(DLXnode *ptr){
    ptr->U->D=ptr->D;
    ptr->D->U=ptr->U;
}

inline void reLR(DLXnode *ptr){
    ptr->L->R=ptr->R->L=ptr;
}

inline void reUD(DLXnode *ptr){
    ptr->U->D=ptr->D->U=ptr;
}

inline void cover(int c){
    if(c==n){
        return;
    }
    delLR(&col[c]);
    DLXnode *R,*C;
    for(C=col[c].D;C!=(&col[c]);C=C->D){
        if(C->c==n){
            continue;
        }
        for(R=C->L;R!=C;R=R->L){
            if(R->c==n){
                continue;
            }
            --sz[R->c];
            delUD(R);
        }
        delLR(C);
    }
}

inline void re(int c){
    if(c==n){
        return;
    }
    DLXnode *R,*C;
    for(C=col[c].U;C!=(&col[c]);C=C->U){
        if(C->c==n){
            continue;
        }
        reLR(C);
        for(R=C->R;R!=C;R=R->R){
            if(R->c==n){
                continue;
            }
            ++sz[R->c];
            reUD(R);
        }
    }
    reLR(&col[c]);
}

bool dance(int k){
    if(head.L==(&head)){
        for(int i=0;i<k;i++){
            printf("%d ",ans[i]);
        }
        return true;
    }
    int INF=(1<<30),c=-1;
    for(DLXnode *ptr=head.L;ptr!=(&head);ptr=ptr->L){
        if(sz[ptr->c]<INF){
            INF=sz[ptr->c];
            c=ptr->c;
        }
    }
    cover(c);
    DLXnode *ptr;
    for(ptr=col[c].D;ptr!=(&col[c]);ptr=ptr->D){
        DLXnode *rc;
        ptr->R->L=ptr;
        for(rc=ptr->L;rc!=ptr;rc=rc->L){
            cover(rc->c);
        }
        ptr->R->L=ptr->L;
        ans[k]=ptr->r+1;
        if(dance(k+1)){
            return true;
        }
        ptr->L->R=ptr;
        for(rc=ptr->R;rc!=ptr;rc=rc->R){
            re(rc->c);
        }
        ptr->L->R=ptr->R;
    }
    re(c);
    return false;
}

int main(){
    scanf("%d %d",&m,&n);
    init(m,n);
    int sr;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&sr);
            if(sr==1){
                addnode(i,j);
            }
        }
    }
    if(!dance(0)){
        cout<<"No Solution!"<<endl;
    }
}

题解 P4929 【【模板】舞蹈链（DLX）】

关于精确覆盖问题

搜索与回溯

X算法

考虑存图方法

Let's dance！

完整代码