笔记 - 精确覆盖问题,重复覆盖问题与 DLX

DLX (Dancing Links X) 是一种用于解决精确覆盖问题的优美算法

https://cplib.tifa-233.com/src/code/util/dlx.hpp 存放了笔者对该算法 / 数据结构的最新实现,建议前往此处查看相关代码

精确覆盖问题

定义 精确覆盖问题

对有限集 \(S=\{a_i|i\in[1,n]\cap\mathbb{N}\}\), 给定集合 \(T=\{T_i\subseteq S|i\in[1,m]\cap\mathbb{N}\}\), 设 \(T^*:=\{T_i^*|i\in[1,l]\cap\mathbb{N},l\leqslant m\}\subseteq 2^T\) 满足

  • \(\displaystyle\bigcup_{T_i^*\in T^*} T_i^*=S\)
  • \(\forall A,B\in T^*,A\cap B\ne\varnothing\iff A=B\)

称 寻找 \(T^*\) 这一问题为精确覆盖问题

换句话说就是在给定的 \(S\) 若干子集中寻找能精确覆盖 \(S\) 的部分

精确覆盖指 \(S\) 中任意元素在这些集合中恰好出现一次

如设

\[ S=\{1,2,3,4,5,6,7\} \]

\[ \begin{matrix} T_1 =\{1,4,7\}&T_2 =\{3,5,6\}&T_3 =\{4,5,7\}&T_4 =\{2,7\}\phantom{,1}\\ T_5 =\{1,4\}\phantom{,1}&T_6 =\{3,6\}\phantom{,1}&T_7 =\{2,3,6\}&T_8 =\{1,4,6\} \end{matrix} \]

\(\{T_2,T_4,T_5\}\) 即是我们要找的解

X 算法

X 算法即是一种用于解决精确覆盖问题的算法,在介绍其流程前,我们先做一些必要的准备工作

以上节例子为例,我们先画个这样的表格

\[ \def\arraystretch{1.5} \begin{array}{c|ccccccc} \texttt{head}&1&2&3&4&5&6&7\\ \hline 1&1&0&0&1&0&0&1\\ 2&0&0&1&0&1&1&0\\ 3&0&0&0&1&1&0&1\\ 4&0&1&0&0&0&0&1\\ 5&1&0&0&1&0&0&0\\ 6&0&0&1&0&0&1&0\\ 7&0&1&1&0&1&0&0\\ 8&1&0&0&1&0&1&0\\ \end{array} \]

其中第 \(i\) 行第 \(j\) 列表示 \(T_i\) 内是否有 \(a_j\), \(1\) 代表有,\(0\) 代表没有

可以记作

\[ \begin{matrix} \texttt{h} & \begin{matrix} 1&2&3&4&5&6&7 \end{matrix} \\ \begin{matrix} 1\\2\\3\\4\\5\\6\\7\\8 \end{matrix} & \begin{bmatrix} 1&0&0&1&0&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&0&1\\ 0&1&0&0&0&0&1\\ 1&0&0&1&0&0&0\\ 0&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ \end{bmatrix} \end{matrix} \]

为了方便查看,我们省去多余成分,并将其看作矩阵,即

\[ \begin{bmatrix} 1&0&0&1&0&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&0&1\\ 0&1&0&0&0&0&1\\ 1&0&0&1&0&0&0\\ 0&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ \end{bmatrix} \]

为了方便之后的叙述,我们做如下约定

表达式含义
\(w\)矩阵宽度
\(h\)矩阵高度
\(N\)所有结点构成的集合
\(R(i)\)\(i\) 行的所有结点,
或 结点 \(i\) 所在行的所有结点,
或 结点集 \(i\) 中所有结点所在行的所有结点
\(C(i)\)\(i\) 列的所有结点,
或 结点 \(i\) 所在列的所有结点,
或 结点集 \(i\) 中所有结点所在列的所有结点
\(r(i)\)结点 \(i\) 的对应行
\(c(i)\)结点 \(i\) 的对应列

X 算法的流程如下

此时我们认为矩阵中的元素即为结点

  1. 选取 \(|R(l)|>0\) 的行 \(l\)
  2. 如果没有可选行或尝试了所有可选的行仍未找到可行解,则无解,返回上一层
  3. 记录 \(r(l)\)
  4. 标记并删除 \(R(l)\), \(C(R(l))\)\(R(C(R(l)))\)
  5. 若矩阵为空矩阵
    1. \(R(l)\) 里结点全为 \(1\), 则说明找到了一组可行解,输出所有标记的编号并退出
    2. \(R(l)\) 里结点有 \(0\), 则不能构成覆盖,还原删除的结点并返回上一层
  6. 对新矩阵递归调用该算法
  7. 取消 3 并还原删除的结点

估计看到这里的你们是一脸懵逼的,下面我们对上例跑一遍流程

强烈建议初学者手动模拟一遍

Show / HideGo to the end

\[ \begin{bmatrix} 1&0&0&1&0&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&0&1\\ 0&1&0&0&0&0&1\\ 1&0&0&1&0&0&0\\ 0&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ \end{bmatrix} \]

  • 首先我们定义栈 \(A\) 用于存储枚举列的编号,初始时 \(A\) 为空

  • 选取第 \(1\) 行,\(A=\{1\}\)

  • 标记 \(R(1)\), \(C(R(1))\)(第 \(1,4,7\) 列), \(R(C(R(1)))\) (第 \(3,4,5,8\) 列)

    我们将三次标记的部分分别染成暗品红色 , 暗黄色 , 暗青色 , 分三次展示

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&0&1\\ 0&1&0&0&0&0&1\\ 1&0&0&1&0&0&0\\ 0&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ \end{bmatrix} \]

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 1\\ \y 0&0&1&\y 0&1&1&\y 0\\ \y 0&0&0&\y 1&1&0&\y 1\\ \y 0&1&0&\y 0&0&0&\y 1\\ \y 1&0&0&\y 1&0&0&\y 0\\ \y 0&0&1&\y 0&0&1&\y 0\\ \y 0&1&1&\y 0&1&0&\y 0\\ \y 1&0&0&\y 1&0&1&\y 0\\ \end{bmatrix} \]

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 1\\ \y 0&0&1&\y 0&1&1&\y 0\\ \y 0&\c 0&\c 0&\y 1&\c 1&\c 0&\y 1\\ \y 0&\c 1&\c 0&\y 0&\c 0&\c 0&\y 1\\ \y 1&\c 0&\c 0&\y 1&\c 0&\c 0&\y 0\\ \y 0&0&1&\y 0&0&1&\y 0\\ \y 0&1&1&\y 0&1&0&\y 0\\ \y 1&\c 0&\c 0&\y 1&\c 0&\c 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素

    新矩阵即为

    \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(1\) 行,其在原矩阵中对应编号为 \(2\), \(A=\{1,2\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 0&\m 1&\m 1&\m 1\\ \c 0&\y 1&\y 0&\y 1\\ \c 1&\y 1&\y 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵,但第一次标记的行非全 \(1\), 所以返回上一层,\(A=\{1\}\) \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(2\) 行,其在原矩阵中对应编号为 \(6\), \(A=\{1,6\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \c 0&\y 1&\c 1&\y 1\\ \m 0&\m 1&\m 0&\m 1\\ \c 1&\y 1&\c 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵,但第一次标记的行非全 \(1\), 所以返回上一层,\(A=\{1\}\) \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(3\) 行,其在原矩阵中对应编号为 \(7\), \(A=\{1,7\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \y 0&\y 1&\y 1&\c 1\\ \y 0&\y 1&\y 0&\c 1\\ \m 1&\m 1&\m 1&\m 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵,但第一次标记的行非全 \(1\), 返回上一层,\(A=\{1\}\)

    \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 我们已经选过所有行但均未找到可行解,返回上一层,\(A=\{\}\) \[ \begin{bmatrix} 1&0&0&1&0&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&0&1\\ 0&1&0&0&0&0&1\\ 1&0&0&1&0&0&0\\ 0&0&1&0&0&1&0\\ 0&1&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ \end{bmatrix} \]

  • 选取第 \(2\) 行,\(A=\{2\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} 1&0&\y 0&1&\y 0&\y 0&1\\ \m 0&\m 0&\m 1&\m 0&\m 1&\m 1&\m 0\\ \c 0&\c 0&\y 0&\c 1&\y 1&\y 0&\c 1\\ 0&1&\y 0&0&\y 0&\y 0&1\\ 1&0&\y 0&1&\y 0&\y 0&0\\ \c 0&\c 0&\y 1&\c 0&\y 0&\y 1&\c 0\\ \c 0&\c 1&\y 1&\c 0&\y 1&\y 0&\c 0\\ \c 1&\c 0&\y 0&\c 1&\y 0&\y 1&\c 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} 1&0&1&1\\ 0&1&0&1\\ 1&0&1&0\\ \end{bmatrix} \]

  • 选取第 \(1\) 行,其在原矩阵中对应编号为 \(1\), \(A=\{2,1\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 1&\m 1\\ \y 0&\c 1&\y 0&\y 1\\ \y 1&\c 0&\y 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵,但第一次标记的行非全 \(1\), 返回上一层,\(A=\{2\}\) \[ \begin{bmatrix} 1&0&1&1\\ 0&1&0&1\\ 1&0&1&0\\ \end{bmatrix} \]

  • 选取第 \(2\) 行,其在原矩阵中对应编号为 \(4\), \(A=\{2,4\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \c 1&\y 0&\c 1&\y 1\\ \m 0&\m 1&\m 0&\m 1\\ 1&\y 0&1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} 1&1 \end{bmatrix} \]

  • 选取第 \(1\) 行,其在原矩阵中对应编号为 \(5\), \(A=\{2,4,5\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 1 \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵,且第一次标记的行全为 \(1\), 说明我们找到了可行解,返回 \(A=\{2,4,5\}\), 即 \(\{T_2,T_4,T_5\}\) 是我们要找的解

Go back

DLX

我们发现 X 算法涉及大量的删除 / 恢复某行 & 列,所以如果只是暴力实现,即使它很高效,我们也很难接受其巨大的常数

所幸真神 Donald E. Knuth 设计了一个数据结构 (双向十字链表) 使得上述操作能高效实现,同时代码还足够简洁 (原文 点此下载)

因为在双向十字链表上进行删除和恢复操作时可看作是指针在不停跳动,所以这个数据结构又被称为舞蹈链 (Dancing links), 用舞蹈链优化的 X 算法就被叫做 DLX 算法 (Dancing Links X algorithm)

对于舞蹈链中的一个结点,其连接方式如下

其删除与恢复自然和双向链表一致

我们看看对下例建立的舞蹈链是什么样子的

\[ \def\arraystretch{1.5} \begin{array}{c:ccccccc} \texttt{head}&1&2&3&4&5&6&7\\ \hline 1&1&0&0&1&0&0&1\\ 2&0&0&1&0&1&1&0\\ 3&0&0&0&1&1&0&1\\ 4&0&1&0&0&0&0&1\\ 5&1&0&0&1&0&0&0\\ 6&0&0&1&0&0&1&0\\ 7&0&1&1&0&1&0&0\\ 8&1&0&0&1&0&1&0\\ \end{array} \]

这回我们略去所有的 \(0\), 因为其不会在链表里出现

\[ \begin{matrix} \texttt{head}&1&2&3&4&5&6&7\\ \texttt{1}&1& & &1& & &1\\ \texttt{2}& & &1& &1&1& \\ \texttt{3}& & & &1&1& &1\\ \texttt{4}& &1& & & & &1\\ \texttt{5}&1& & &1& & & \\ \texttt{6}& & &1& & &1& \\ \texttt{7}& &1&1& &1& & \\ \texttt{8}&1& & &1& &1& \\ \end{matrix} \]

对应的舞蹈链就是这样的

代码具体如何实现呢

建议在看完准备工作后自行尝试实现初始化,删除与恢复操作

准备工作

存储

对于任意一个结点,其均具有 4 个指针,也就是

Show code

`

我们也可以用内存池存储

Show code

`

其次,我们还需要记录结点所在行和列的编号,最后结点的代码如下

Show code

`

除此之外我们还需如下变量

  • width : 宽度 (即 \(|S|\))
  • height : 高度 (即 \(|B|\))
  • cnt_col[] : 每一列的结点数,用于常数优化

最后代码如下

Show code

`

  • Q: head 结点,行首结点和列首结点存在哪里

    A: 实际上

    • 行首结点是虚拟结点,不需要存

    • head 结点存为 node[0]

    • \(i\) 列的首结点存为 node[i]

  • Q: 常数优化是什么

    A: 见 此节内容

另外

  • 为了方便后面写代码,我们做如下宏定义

    Show code

    `

初始化

分成两步

  • 存入 head 结点和列首结点
  • 存入其他结点
存入 head 结点和列首结点

Show code

`

存入其他结点

在实现中往往是顺次插入 \(R(1)\)\(R(h)\) 的,此时当我们插入某个点 x 时,我们发现:

  • node[x].l 即为上一个插入的结点下标,即 x-1
  • node[x].r 即为第一个插入的结点下标
  • node[x].u 即为列首结点上方结点的下标,即_u(_col(x))
  • node[x].d 即为列首结点下标,即_col(x)

代码实现如下

Show code

求解

删除

我们这样定义删除操作 remove:

  • 接收一个参数_col: 代表要删除的列
  • 功能是删除某一列和与这一列相交的所有行

结合该图我们不难写出代码

Show code

恢复

恢复操作和删除操作类似,在此不再赘述

Show code


上面的都是舞蹈链的操作,接下来才是重点

dance

我们根据舞蹈链的性质,对 X 算法流程进行一些调整

  1. 选取某一列 \(i\) 并对其执行 remove 操作
  2. 枚举 \(C(i)\) 中的结点 \(j\)
    1. 记录 \(r(j)\), 对 \(R(j)\) 中所有结点的列编号执行 remove 操作
    2. node[head].r == head, 则说明找到了解,对 \(R(j)\) 中所有结点的列编号执行 resume 操作并返回 true
    3. \(R(j)\) 中所有结点的列编号执行 resume 操作
  3. 对列 \(i\) 中所有结点的列编号执行 resume 操作
  4. 返回 false

我们注意到第一步中选取的列不影响最终答案,所以我们可以加个常数优化,即选取 \(|C(i)|\) 最小的 \(i\)

值得注意的是,\(R(j)\) 删除的顺序和恢复的顺序是相反的,即若你删除行中结点是从左向右删,则恢复时要从右向左恢复 (类比递归和回溯的顺序关系)

如果相同则会显著降低代码速度,具体在后文讲述

我们可以结合例子模拟一遍

Show / HideGo to the end

我们不考虑常数优化,每次只选取 node[head].r 删除,则一共会执行 \(13\)remove 操作和 \(6\)resume 操作

  1. remove 1

  2. remove 4 & remove 7

  3. remove 2

  4. remove 3 & remove 5

  5. remove 6

  6. resume 6

  7. resume 5 & resume 3

  8. resume 2

  9. resume 7 & resume 4

  10. remove 4

  11. remove 2

  12. remove 7

  13. remove 3

  14. remove 5 & remove 6

Go back

加上常数优化后,代码就是这样的

Show code

关于删除和恢复的顺序

我在上面说过:删除和恢复的方向相同时速度会显著变慢,这里举一例来具体说明

以下图为例

首先我们先删除

操作结果
remove 1
remove 3
remove 4

之后我们恢复

方向相反 1方向相同 2
resume 4
resume 1
resume 3
resume 3
resume 1
resume 4

我们注意到这两种方式都是正确的,但是如果删除和恢复的方向相同,则会重复恢复更多结点,连带着也会重复赋值更多指针,所以就会变慢

比较极端的情况可以在 洛谷 P1074 靶形数独 中的数据点 #13 找到,两种不同的恢复顺序能使得最后时间相差十多倍

时间复杂度

不难发现是 \(O(c^n)\) 的,其中 \(c\) 是个接近 \(1\) 的数,\(n\) 是舞蹈链中结点个数

在实际应用中,因为 \(c\) 足够接近 \(1\), 所以 DLX 效率很高

例题

  • 洛谷 P4929 【模板】舞蹈链(DLX)

    Show code

    Luogu_P4929view raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    /*
    * @Author: Tifa
    * @Description: From <https://github.com/Tiphereth-A/CP-archives>
    * !!! ATTENEION: All the context below is licensed under a
    * GNU Affero General Public License, Version 3.
    * See <https://www.gnu.org/licenses/agpl-3.0.txt>.
    */
    #include <bits/stdc++.h>
    using namespace std;
    template <typename Val_t = int,
    typename ID_t = int,
    const std::size_t _Edge_len = 500 + 5,
    const std::size_t _Node_size = 7000 + 5>
    class DLX {
    private:
    struct Node {
    ID_t l, r, u, d;
    ID_t row, col;
    } node[_Node_size];
    std::size_t width, height;
    std::size_t cnt_node;
    std::size_t cnt_col[_Edge_len];
    #define __l(id) node[id].l
    #define __r(id) node[id].r
    #define __u(id) node[id].u
    #define __d(id) node[id].d
    #define __row(id) node[id].row
    #define __col(id) node[id].col
    #define _for(i, start, dir) \
    for (std::size_t i = __##dir(start); i != start; i = __##dir(i))
    void remove_col(std::size_t _col) {
    __r(__l(_col)) = __r(_col);
    __l(__r(_col)) = __l(_col);
    _for(i, _col, d)
    _for(j, i, r) {
    __u(__d(j)) = __u(j);
    __d(__u(j)) = __d(j);
    --cnt_col[__col(j)];
    }
    }
    void restore_col(std::size_t _col) {
    __r(__l(_col)) = __l(__r(_col)) = _col;
    _for(i, _col, u)
    _for(j, i, r) {
    __u(__d(j)) = __d(__u(j)) = j;
    ++cnt_col[__col(j)];
    }
    }
    std::size_t find_min_col() {
    std::size_t res = __r(0);
    _for(i, 0, r)
    if (cnt_col[i] < cnt_col[res]) res = i;
    return res;
    }
    bool dance(ID_t *_ans, std::size_t &_len) {
    if (__r(0) == 0) return true;
    std::size_t now_r = find_min_col();
    remove_col(now_r);
    _for(i, now_r, d) {
    _ans[++_len] = __row(i);
    _for(j, i, r) remove_col(__col(j));
    if (dance(_ans, _len)) return true;
    --_len;
    _for(j, i, l) restore_col(__col(j));
    }
    restore_col(now_r);
    return false;
    }

    public:
    void clear() {
    memset(node, 0, sizeof(node));
    memset(cnt_col, 0, sizeof(cnt_col));
    width = height = cnt_node = 0;
    }
    void init(std::size_t _width, std::size_t _height) {
    width = cnt_node = _width;
    height = _height;
    for (std::size_t i = 1; i <= width; ++i)
    node[i] = {i - 1, i + 1, i, i, 0, i};
    node[__r(width) = 0] = {width, 1, 0, 0, 0, 0};
    }
    void insert_row(std::size_t _ln, ID_t *_cols, std::size_t _len_cols) {
    for (std::size_t i = 1; i <= _len_cols; ++i) {
    node[cnt_node + i] = {cnt_node + i - 1,
    cnt_node + i + 1,
    __u(_cols[i]),
    _cols[i],
    _ln,
    _cols[i]};
    __d(__u(_cols[i])) = cnt_node + i;
    __u(_cols[i]) = cnt_node + i;
    ++cnt_col[_cols[i]];
    if (__d(_cols[i]) == _cols[i]) __d(_cols[i]) = cnt_node + i;
    }
    __l(cnt_node + 1) = cnt_node + _len_cols;
    __r(cnt_node + _len_cols) = cnt_node + 1;
    cnt_node += _len_cols;
    }
    void insert_map(Val_t **_map,
    std::size_t _width,
    std::size_t _height,
    std::size_t _height_phy = _Edge_len) {
    ID_t *_ = (ID_t *)malloc(sizeof(ID_t) * (_width + 1));
    for (std::size_t _ln = 1, len; _ln <= _height; ++_ln) {
    len = 0;
    for (std::size_t _col = 1; _col <= _width; ++_col)
    if (*((Val_t *)_map + _ln * _height_phy + _col)) _[++len] = _col;
    if (len) insert_row(_ln, _, len);
    }
    free(_);
    }
    bool operator()(ID_t *ans, std::size_t &len) {
    len = 0;
    return dance(ans, len);
    }
    #undef __l
    #undef __r
    #undef __u
    #undef __d
    #undef __row
    #undef __col
    #undef _for
    };
    DLX<> a;
    const int N = 505;
    int n, m;
    int maps[N][N];
    int ans[N];
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> maps[i][j];
    a.init(m, n);
    a.insert_map((int **)maps, m, n, N);
    std::size_t len_ans = 0;
    if (a((int *)ans, len_ans))
    for (int i = 1; i <= len_ans; ++i) cout << ans[i] << " ";
    else cout << "No Solution!";
    return 0;
    }
  • 洛谷 P1074 靶形数独 -> 题解

  • 洛谷 P4205 [NOI2005] 智慧珠游戏 -> 题解

重复覆盖问题

从字面意思上看,重复覆盖问题只需要将精确覆盖问题里的精确覆盖改为可重复覆盖即可

可重复覆盖指 \(S\) 中任意元素在这些集合中至少出现一次

因为改为可重复覆盖后很容易出现多解,所以我们更关心用于覆盖的集合个数最小的解

所以我们定义重复覆盖问题如下

定义 重复覆盖问题

对有限集 \(S=\{a_i|i\in[1,n]\cap\mathbb{N}\}\), 给定集合 \(T=\{T_i\subseteq S|i\in[1,m]\cap\mathbb{N}\}\), 设 \(T^*:=\{T_i^*|i\in[1,l]\cap\mathbb{N},l\leqslant m\}\subseteq 2^T\) 满足

  • \(\displaystyle\bigcup_{T_i^*\in T^*} T_i^*=S\)
  • \(\displaystyle|T^*|=\min_{T'\in 2^T}\{|T'|\}\)

称 寻找 \(T^*\) 这一问题为重复覆盖问题

解法

解决重复覆盖问题时我们只需省去在精确覆盖问题中三次标记中的最后一次标记即可

而这样做会导致状态空间爆炸,所以我们需要做优化

我们发现这和迭代加深搜索的思想有契合之处,即预设一个最大深度 max_depth (在此处即为预设 \(|B^*|\) 的最大值 \(M\)), 然后尝试求解,根据返回情况调整 max_depth

求解的流程如下

  1. 选取使 \(|C(i)|\) 最小的列 \(i\)
  2. 如果没有可选列或尝试了所有可选列仍未找到可行解,则返回 false
  3. 枚举 \(C(i)\) 中的结点 \(j\)
    1. 记录 \(r(j)\)
    2. 删除 \(R(j),C(j)\)
    3. 若当前已删除了 \(M\) 行且仍为找到结果,则返回 false
    4. 对当前矩阵递归搜索
      1. 若返回 true, 则恢复矩阵并返回 true
    5. 取消记录 \(r(j)\) 并还原删除的结点
  4. 还原删除的结点
  5. 返回 false

我们还可以设计估价函数 \(H\) 来加速求解过程,也就是应用 IDA*

接下来枚举或者二分 max_depth 即可

附模板,输入方式与 洛谷 P4929 【模板】舞蹈链(DLX) 相同

Show code

例题


参考资料


  1. 淡紫色的结点是重复恢复的结点,靛蓝色的指针是重复赋值的指针↩︎

  2. 淡紫色的结点是重复恢复一次的结点,浅紫色的结点是重复恢复两次的结点,靛蓝色的指针是重复赋值一次的指针,枣红色的指针是重复赋值两次的指针↩︎