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

· · 题解

问题提出

给定 N 个待选集合 S_1,S_2,\cdots,S_{N-1},S_N 与一个目标集合 X，求出一个集合 P 使得：

\bigcup_{i\in P}S_i=X

记为性质 1，且：

S_i \cap S_j=\varnothing(i,j\in P,i\ne j)

记为性质 2，这就是精确覆盖问题。

问题转化

同 Luogu P4929 【模板】舞蹈链（DLX） 的叙述，若把集合中的元素化为一个 N 行 M 列的 01 矩阵，那问题即可转换为：

选出矩阵中的若干行，使每一列上有且仅有一行中位上的元素为 1。

算法引入

对于这样一个矩阵，集合 P 为已选的行集：

0&0&1&0&1&1&0\\ 1&1&0&0&0&0&0\\ 1&0&1&0&0&1&0\\ 1&1&1&0&1&0&1\\ 0 &0&0&1&0&0&1 \end{pmatrix} P =\varnothing

要是先选择第一行，我们把第一行涂上红色:

\color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ 1&1&0&0&0&0&0\\ 1&0&1&0&0&1&0\\ 1&1&1&0&1&0&1\\ 0 &0&0&1&0&0&1 \end{pmatrix} P=\{1\}

由性质 2 得：使每一列上有且仅有一行中位上的元素为 1。

那么我们把第一行位上为 1 的列都标记为红色：

\color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ 1&1&\color{red}0&0&\color{red}0&\color{red}0&0\\ 1&0&\color{red}1&0&\color{red}0&\color{red}1&0\\ 1&1&\color{red}1&0&\color{red}1&\color{red}0&1\\ 0 &0&\color{red}0&1&\color{red}0&\color{red}0&1 \end{pmatrix} P=\{1\}

那么这些列上含有 1 的行我们是绝对不能选的，这些行也标记为红色：

\color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ 1&1&\color{red}0&0&\color{red}0&\color{red}0&0\\ \color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}0&\color{red}1&\color{red}0\\ \color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1\\ 0 &0&\color{red}0&1&\color{red}0&\color{red}0&1 \end{pmatrix} P=\{1\}

把它们都删掉，得到：

\begin{pmatrix} 1&1&0&0\\ 0 &0&1&1 \end{pmatrix} P=\{1\}

肉眼很直观的可以看到：把这两行都选上不就好了，但是我们遵守下程序。

先选第 1 行（其实为原矩阵的第 2 行），并标红：

\begin{pmatrix} \color{red}1&\color{red}1&\color{red}0&\color{red}0\\ 0 &0&1&1 \end{pmatrix} P=\{1,2\}

把行中位上为 1 的列标红：

\begin{pmatrix} \color{red}1&\color{red}1&\color{red}0&\color{red}0\\ \color{red}0 &\color{red}0&1&1 \end{pmatrix} P=\{1,2\}

列中全为 0 所以没有第 3 步了，删去后得到：

\begin{pmatrix} 1&1 \end{pmatrix} P=\{1,2\}

再进行一轮后，矩阵为空：

P=\{1,2,5\}

那么 P 则为精确覆盖问题的一个解。

但实际上，这是因为我们的数据很弱，导致我们一次就求出来了，但是在一般情况下，一次性是无法得到正解的，若矩阵在搜索的过程中，只剩 0 元素，无法再选择，则恢复一次选择，在写代码时使用回溯的手段解决。

数据结构引入

著名的图灵奖得主:尼古拉斯·沃斯 提出著名的等式:

        程序 = 算法 + 数据结构。

我们已经研究出了解决这个精确覆盖的算法，那我们怎么通过选用数据结构来解决？

Donald E. Knuth 使用了 十字双向循环链表 来解决这个问题

他把我们刚才用的矩阵拿双向十字链表维护，不同的是，他只维护了其中的 1 元素。

既然是双向十字链表，那么每个节点都具有 4 个指针域，在此定义：

U[i] 指向 i 上方的元素， D[i] 指向 i 下方的元素， L[i] 指向 i 左方的元素， R[i] 指向 i 右方的元素。

特殊得，每一列上都有一个节点（独立的，不代表这里是 1），称为列头，在后辅助我们对算法的应用。

每一行中任取一个节点作为行首（在代码实现中为第一个插入到本行的元素，并不是独立的，代表位上为 1）。

还有一个独立的 0 节点，不参与算法实现过程，只是在后用于辅助判断矩阵是否为空。

所以这个链表实际上长这样：

程序实现

接下来就到写代码阶段啦！

变量初始化

int L[Maxs],R[Maxs],U[Maxs],D[Maxs],Ans[Maxs],Col[Maxs],Row[Maxs],Siz[Maxs],Head[Maxs],n,m,tot;

Ans 数组存我们搜索过程中选择的行；

Col 与 Row 分别为存节点的列与行；

Siz 存列上元素的个数；

Head 存行首的下标；

n,m 分别为矩阵的行数与列数；

tot 存当前节点的个数。

1 建初始表

我们只需要把 0 节点与各列列头建好即可，给出代码：

inline void build(int r,int c)//建立 r 行 c 列表
{
    n=r,m=c;//赋值
    for(rei i=0;i<=c;i++)  L[i]=i-1,R[i]=i+1,U[i]=D[i]=i;
   //左边为 i-1 ，右边为 i+1.上边与下边都为 i
    L[0]=c,R[c]=0,tot=c;
   // 0的左边是 c，c的右边是 0，构成循环链表
   //目前有 c 个节点（0节点不占）
}

2 插入节点

对于列上，我们已经有独立的列头节点，把新节点放在插入到列头下方。

对于行上，若行首为空，那么把行首赋为当前节点，左指针右指针初始化指向当前节点；

若行首不为空，则插在行首右侧

注：我们在实现算法的过程中操作都是对整行整列的，所以其在链表中的顺序不重要，只要保证在正确的行列上即可。

给出代码：

inline void insert(int r,int c)
{
    Col[++tot]=c,Row[tot]=r,Siz[c]++;
    D[tot]=D[c],U[D[c]]=tot,U[tot]=c,D[c]=tot;
    if(!Head[r]) Head[r]=L[tot]=R[tot]=tot;
    else 
    {
        R[tot]=R[Head[r]],L[R[Head[r]]]=tot;
        L[tot]=Head[r],R[Head[r]]=tot;
    }
}

3 删除一整列，并把其位上为 1 的行删去

先对列头进行处理，再对列上元素进行遍历，再把遍历列节点所在行删去即可。

注：此处遍历为对循环链表的遍历，不会的可以自己推一下

给出代码与删除行上元素示意图：

#define rei register int
inline void remove(int c)
{
    L[R[c]]=L[c],R[L[c]]=R[c];
    for(rei i=D[c];i!=c;i=D[i]) 
        for(rei j=R[i];j!=i;j=R[j])
            U[D[j]]=U[j],D[U[j]]=D[j],Siz[Col[j]]--;
}

4 上一个操作的回溯

即为逆操作，注意每一个地方都是逆的，不要漏了。

注：在这个操作中你就会感到循环链表有多妙了，删除这一列/行后，节点的信息并没有改变，所以很容易恢复。

#define rei register int
inline void recover(int c)
{
    for(rei i=U[c];i!=c;i=U[i]) 
        for(rei j=L[i];j!=i;j=L[j])
            U[D[j]]=D[U[j]]=j,Siz[Col[j]]++;
    L[R[c]]=R[L[c]]=c;
}

5 搜索

每一次贪心的选择 Siz 较小的列，然后删除这一列后枚举选择一行并删除这一行位上为 1 的列，这样使得 Siz 较大的列很有可能在过程中被删除，降低回溯的次数。 

#define rei register int 
inline bool dance(int dep)//已选行数为 dep-1 
{
    if(!R[0])//矩阵为空，输出，跳出
    {
        for(int i=1;i<dep;i++) printf("%d ",Ans[i]);
        return 1;
    }
    rei c=R[0];
    for(rei i=R[0];i;i=R[i]) if(Siz[i]<Siz[c]) c=i;
    remove(c);//找到 Siz 最小列并删除
    for(rei i=D[c];i!=c;i=D[i])
    {
        Ans[dep]=Row[i];
        for(rei j=R[i];j!=i;j=R[j]) remove(Col[j]);//删除位上为 1 的列
        if(dance(dep+1)) return 1;//如果已经找到答案，跳出
        for(rei j=L[i];j!=i;j=L[j]) recover(Col[j]);//回溯后继续找
    }
    recover(c);
    return 0;//回溯，这种情况无解
}

给出 Dancing Links 部分代码：

#define rei register int 
struct DLX {
    int L[Maxs],R[Maxs],U[Maxs],D[Maxs],Ans[Maxs],Col[Maxs],Row[Maxs],Siz[Maxs],Head[Maxs],n,m,tot;
    inline void build(int r,int c)
    {
        n=r,m=c;
        for(rei i=0;i<=c;i++) L[i]=i-1,R[i]=i+1,U[i]=D[i]=i;
        L[0]=c,R[c]=0,tot=c;
    }
    inline void insert(int r,int c)
    {
        Col[++tot]=c,Row[tot]=r,Siz[c]++;
        D[tot]=D[c],U[D[c]]=tot,U[tot]=c,D[c]=tot;
        if(!Head[r]) Head[r]=L[tot]=R[tot]=tot;
        else 
        {
            R[tot]=R[Head[r]],L[R[Head[r]]]=tot;
            L[tot]=Head[r],R[Head[r]]=tot;
        }
    }
    inline void remove(int c)
    {
        L[R[c]]=L[c],R[L[c]]=R[c];
        for(rei i=D[c];i!=c;i=D[i]) for(rei j=R[i];j!=i;j=R[j]) U[D[j]]=U[j],D[U[j]]=D[j],Siz[Col[j]]--;
    }
    inline void recover(int c)
    {
        for(rei i=U[c];i!=c;i=U[i]) for(rei j=L[i];j!=i;j=L[j]) U[D[j]]=D[U[j]]=j,Siz[Col[j]]++;
        L[R[c]]=R[L[c]]=c;
    }
    inline bool dance(int dep)
    {
        if(!R[0])
        {
            for(int i=1;i<dep;i++) printf("%d ",Ans[i]);
            return 1;
        }
        rei c=R[0];
        for(rei i=R[0];i;i=R[i]) if(Siz[i]<Siz[c]) c=i;
        remove(c);
        for(rei i=D[c];i!=c;i=D[i])
        {
            Ans[dep]=Row[i];
            for(rei j=R[i];j!=i;j=R[j]) remove(Col[j]);
            if(dance(dep+1)) return 1;
            for(rei j=L[i];j!=i;j=L[j]) recover(Col[j]);
        }
        recover(c);
        return 0;
    }
}dlx;