Dancing Links

精确覆盖问题

定义

精确覆盖问题 (Exact Cover Problem) 是指给定许多集合 S_i (1 \le i \le n) 以及一个集合 X ，求满足以下条件的无序多元组 (T_1, T_2, \cdots , T_m) ：

(1) \forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j)

(2) X = \bigcup\limits_{i = 1}^{m}T_i

(3) \forall i \in[1, m], T_i \in \{S_1, S_2, \cdots, S_n\}

例如，若给出

\begin{aligned} & S_1 = \{5, 9, 17\} \\ & S_2 = \{1, 8, 119\} \\ & S_3 = \{3, 5, 17\} \\ & S_4 = \{1, 8\} \\ & S_5 = \{3, 119\} \\ & S_6 = \{8, 9, 119\} \\ & X = \{1, 3, 5, 8, 9, 17, 119\} \end{aligned}

则 (S_1, S_4, S_5) 为一组合法解。

问题转化

我们将 \bigcup\limits_{i = 1}^{n}S_i 中的所有数离散化，那么可以得到这么一个模型：

给定一个 01 矩阵，你可以选择一些行，使得最终每列都恰好有一个 1。 举个例子，我们对上文中的例子进行建模，可以得到这么一个矩阵：

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

其中第 i 行表示着 S_i ，而这一行的每个数依次表示 [1 \in S_i],[3 \in S_i],[5 \in S_i],\cdots,[119 \in S_i] 。

暴力 1

我们可以枚举选择哪些行，最后检查这个方案是否合法。

因为每一行都有选或者不选两种状态，所以枚举行的时间复杂度是 O(2^n) 的；

而每次检查都需要 O(nm) 的时间复杂度。所以总的复杂度是 O(nm\cdot2^n) 。

代码实现 
int ok = 0;
for(int state = 0; state < 1 << n; ++state) { // 枚举每行是否被选
  for(int i = 1; i <= n; ++i) if((1 << i - 1) & state)
    for(int j = 1; j <= m; ++j)
      a[i][j] = 1;
  int flag = 1;
  for(int j = 1; j <= m; ++j) for(int i = 1, bo = 0; i <= n; ++i)
    if(a[i][j]) {
      if(bo) flag = 0;
      else bo = 1;
    }
  if(!flag) continue;
  else {
    ok = 1;
    for(int i = 1; i <= n; ++i) if((1 << i - 1) & state)
        printf("%d ", i);
    puts("");
  }
  memset(a, 0, sizeof(a));
}
if(!ok) puts("No solution.");

暴力 2

考虑到 01 矩阵的特殊性质，我们可以把每一行都看做成一个 m 位二进制数。

因此被转化为了

给你 n 个 m 位二进制数，要求选择一些数，使得任意两个数的与都为 0，且所有数的或为 2^m - 1 。 tmp 表示的是截至目前的所有被选择了的 m 位二进制数的或。

因为每一行都有选或者不选两种状态，所以枚举行的时间复杂度为 O(2^n) ；

而每次计算 tmp 都需要 O(n) 的时间复杂度。所以总的复杂度为 O(n\cdot2^n) 。

代码实现 
int ok = 0;
for(int i = 1; i <= n; ++i)
  for(int j = m; j >= 1; --j)
    num[i] = num[i] << 1 | a[i][j];
for(int state = 0; state < 1 << n; ++state) {
  int tmp = 0;
  for(int i = 1; i <= n; ++i)  if((1 << i - 1) & state) {
    if(tmp & num[i]) break;
    tmp |= num[i];
  }
  if(tmp == (1 << m) - 1) {
    ok = 1;
    for(int i = 1; i <= n; ++i) if((1 << i - 1) & state)
      printf("%d ", i);
      puts("");
  }
}
if(!ok) puts("No solution.");

X 算法

Donald E. Knuth 提出了 X 算法 (Algorithm X)，其思想与刚才的暴力差不多，但是方便优化。

继续以上文中中提到的例子为载体，我们得到的是一个这样的 01 矩阵：

\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}
  1. 此时第一行有 3 个 1 ，第二行有 3 个 1 ，第三行有 3 个 1 ，第四行有 2 个 1 ，第五行有 2 个 1 ，第六行有 3 个 1 。选择第一行，将它删除，并将所有 1 所在的列打上标记；
\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 1 & \color{Red}1 & 0 & \color{Red}0 & \color{Red}1 & 0 \\ 1 & 0 & \color{Red}0 & 1 & \color{Red}0 & \color{Red}0 & 0 \\ 0 & 1 & \color{Red}0 & 0 & \color{Red}0 & \color{Red}0 & 1 \\ 0 & 0 & \color{Red}0 & 1 & \color{Red}1 & \color{Red}0 & 1 \end{pmatrix}
  1. 选择所有被标记的列，将它们删除，并将这些列中含 1 的行打上标记；
\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}1 & \color{Blue}1 & \color{Red}0 & \color{Blue}0 & \color{Blue}1 & \color{Red}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Red}0 & \color{Red}0 & \color{Blue}0 & \color{Red}1 & \color{Blue}1 & \color{Blue}0 & \color{Red}1 \end{pmatrix}
  1. 选择所有被标记的行，将它们删除；
\begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}

这表示表示我们选择了一行，且这一行的所有 1 所在的列不能有其他 1 了 。

于是我们得到了这样的一个新的小 01 矩阵：

\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}
  1. 此时第一行（原来的第二行）有 3 个 1 ，第二行（原来的第四行）有 2 个 1 ，第三行（原来的第五行）有 2 个 1 。选择第一行（原来的第二行），将它删除，并将所有 1 所在的列打上标记；
\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Red}1 & 0 & \color{Red}1 & \color{Red}0 \\ \color{Red}0 & 1 & \color{Red}0 & \color{Red}1 \end{pmatrix}
  1. 选择所有被标记的列，将它们删除，并将这些列中含 1 的行打上标记；
\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Red}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}
  1. 选择所有被标记的行，将它们删除；
\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}

于是我们得到了一个空矩阵。但是上次删除的行 "1 0 1 1" 不是全 1 的，说明选择有误；

\begin{pmatrix} \end{pmatrix}
  1. 回溯到步骤 4 ，我们考虑选择第二行（原来的第四行），将它删除，并将所有 1 所在的列打上标记；
\begin{pmatrix} \color{Red}1 & 0 & \color{Red}1 & 1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Red}0 & 1 & \color{Red}0 & 1 \end{pmatrix}
  1. 选择所有被标记的列，将它们删除，并将这些列中含 1 的行打上标记；
\begin{pmatrix} \color{Blue}1 & \color{Red}0 & \color{Blue}1 & \color{Red}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix}
  1. 选择所有被标记的行，将它们删除；
\begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix}

于是我们得到了这样的一个矩阵：

\begin{pmatrix} 1 & 1 \end{pmatrix}
  1. 此时第一行（原来的第五行）有 2 个 1 ，将它们全部删除，我们得到了一个空矩阵：
\begin{pmatrix} \end{pmatrix}

  1. 上一次删除的时候，删除的是全 1 的行，因此成功，算法结束。

    答案即为我们删除的三行： 1, 4, 5 。

  2. 强烈建议自己模拟一遍矩阵删除、还原与回溯的过程后再接着阅读下文。

我们可以概括出 X 算法的过程：

  1. 对于现在的矩阵 M ，选择并标记一列 r ，将 r 添加至 S 中；

  2. 如果尝试了所有的 r 却无解，则算法结束，输出无解。

  3. 标记与 r 相关的行 r_i 和 c_i ；

  4. 删除所有标记的行和列，得到新矩阵 M' ；

  5. 如果 M' 为空，且 r 为全 1 的，则算法结束，输出被删除的行组成的集合 S ；

    如果 M' 为空，且 r 不为全 1 的，则恢复与 r 相关的行 r_i 以及列 c_i ，跳转至步骤 1 ；

    如果 M' 不为空，则跳转至步骤 1 ；

不难看出，X 算法需要大量的“删除行”、“删除列”和“恢复行”、“恢复列”的操作。

Donald E. Knuth 想到了用双向十字链表来维护这些操作。

而在双向十字链表上不断跳跃的过程被形象地比喻成“跳跃”，因此被用来优化 X 算法的双向十字链表也被称为“Dancing Links”。

预编译命令

#define IT(i, A, x) for (i = A[x]; i != x; i = A[i])

定义

既然是双向十字链表，那么一定是有四个指针域的：一个指上方的元素，一个指下方的元素，一个指左边的元素，一个指右边的元素。而每个元素 i 在整个双向十字链表系中都对应着一个格子，因此还要表示 i 所在的列和所在的这样：

dlx-1

是不是非常简单？

而其实大型双向链表其实是长这样的：

dlx-2

每一行都有一个行首指示，每一列都有一个列指示。

行首指示为 first[] ，列指示是我们虚拟出的 c + 1 个结点。

同时，每一列都有一个 siz[] 表示这一列的元素个数。

特殊地， 0 号结点无右结点等价于这个 Dancing Links 为空。

static const int MS = 1e5 + 5;
int n, m, idx, first[MS], siz[MS];
int L[MS], R[MS], U[MS], D[MS];
int col[MS], row[MS];

remove 操作

\text{remove(c)} 表示在 Dancing Links 中删除第 c 列以及与其相关的行和列。

我们先将 c 删除，此时：

(1) c 左侧的结点的右结点应为 c 的右结点；

(2) c 右侧的结点的左结点应为 c 的左结点。

即 L[R[c]] = L[c], R[L[c]] = R[c]; 。

dlx-3.png

然后我们要顺着这一列往下走，把走过的每一行都删掉。

如何删掉每一行呢？枚举当前行的指针 j ，此时：

(1) j 上方的结点的下结点应为 j 的下结点；

(2) j 下方的结点的上结点应为 j 的上结点。

注意要修改每一列的元素个数。

即 U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]]; 。

dlx-4.png

因此 \text{remove(c)} 的代码实现就非常简单了：

其中第一个 IT(i, D, c) 等价于 for(i = D[c]; i != c; i = D[i]) ，即在顺着这一列从上往下遍历；

第二个 IT(j, R, i) 等价于 for(j = R[i]; j != i; j = R[j]) ，即在顺着这一行从左往右遍历。

void remove(const int &c) {
  int i, j;
  L[R[c]] = L[c], R[L[c]] = R[c];
  IT(i, D, c) IT(j, R, i) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
}

recover 操作

\text{recover(c)} 表示在 Dancing Links 中还原第 c 列以及与其相关的行和列。

\text{recover(c)} 即 \text{remove(c)} 的逆操作，在这里就不多赘述了。

值得注意的是， \text{recover(c)} 的所有操作的顺序与 \text{remove(c)} 的操作恰好相反。

在这里给出 \text{recover(c)} 的代码实现：

void recover(const int &c) {
  int i, j;
  IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
  L[R[c]] = R[L[c]] = c;
}

build 操作

\text{build(r, c)} 表示新建一个大小为 r \times c ，即有 r 行， c 列的 Dancing Links。

我们新建 c + 1 个结点，为列指示。

第 i 个点的左结点为 i - 1 ，右结点为 i + 1 ，上结点为 i ，下结点为 i 。

特殊地， 0 结点的左结点为 c ， c 结点的右结点为 0 。

于是我们得到了一条链：

dlx-5.png

void build(const int &r, const int &c) {
  n = r, m = c;
  for (int i = 0; i <= c; ++i) {
    L[i] = i - 1, R[i] = i + 1;
    U[i] = D[i] = i;
  }
  L[0] = c, R[c] = 0, idx = c;
  memset(first, 0, sizeof(first));
  memset(siz, 0, sizeof(siz));
}

这样就初始化了一个 Dancing Links。

insert 操作

\text{insert(r, c)} 表示在第 r 行，第 c 列插入一个结点。

我们分两种情况来操作：

(1) 如果第 r 行没有元素，那么直接插入一个元素，并使 first(r) 指向这个元素；

(2) 如果第 r 行有元素，那么将这个新元素 用一种奇异的方式 与 c 和 first(r) 连接起来。

对于 (1)，我们可以通过 first[r] = L[idx] = R[idx] = idx; 来实现；

对于 (2)，（我们称这个新元素为 idx ）：

  • 我们把 idx 插入到 c 的正下方，此时：

    (1) idx 下方的结点为原来 c 的下结点；

    (2) idx 下方的结点（即原来 c 的下结点）的上结点为 idx ;

    (3) idx 的上结点为 c ；

    (4) c 的下结点为 idx 。

    注意记录 idx 的所在列和所在行，以及更新这一列的元素个数。

    col[++idx] = c, row[idx] = r, ++siz[c];
U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;

    强烈建议读者完全掌握这几步的顺序后再继续阅读本文。

  • 我们把 idx 插入到 first(r) 的正右方，此时：

    (1) idx 右侧的结点为原来 first(r) 的右结点；

    (2) 原来 first(r) 右侧的结点的左结点为 idx ；

    (3) idx 的左结点为 first(r) ；

    (4) first(r) 的右结点为 idx 。

    L[idx] = first[r], R[idx] = R[first[r]];
R[first[r]] = idx, L[R[first[r]]] = idx;

    强烈建议读者完全掌握这几步的顺序后再继续阅读本文。

对于 \text{insert(r, c)} 这个操作，我们可以画图来辅助理解：

dlx-6.png

留心曲线箭头的方向。

在这里给出 \text{insert(r, c)} 的代码：

void insert(const int &r, const int &c) {
  row[++idx] = r, col[idx] = c, ++siz[c];
  U[idx] = D[idx] = c, U[D[c]] = idx, D[c] = idx;
  if (!first[r])
    first[r] = L[idx] = R[idx] = idx;
  else {
    L[idx] = first[r], R[idx] = R[first[r]];
    L[R[first[r]]] = idx, R[first[r]] = idx;
  }
}

dance 操作

\text{dance()} 即为递归地删除以及还原各个行列的过程。

(1) 如果 0 号结点没有右结点，那么矩阵为空，记录答案并返回；

(2) 选择列元素个数最少的一列，并删掉这一列；

(3) 遍历这一列所有有 1 的行，枚举它是否被选择；

(4) 递归调用 \text{dance()} ，如果可行，则返回；如果不可行，则恢复被选择的行；

(5) 如果无解，则返回；

在这里给出 \text{dance()} 的代码实现：

bool dance(int dep) {
  int i, j, c = R[0];
  if (!R[0]) {
    ans = dep;
    return 1;
  }
  IT(i, R, 0) if (siz[i] < siz[c]) c = i;
  remove(c);
  IT(i, D, c) {
    stk[dep] = row[i];
    IT(j, R, i) remove(col[j]);
    if (dance(dep + 1)) return 1;
    IT(j, L, i) recover(col[j]);
  }
  recover(c);
  return 0;
}

其中 stk[] 用来记录答案。

注意我们每次优先选择列元素个数最少的一列进行删除，这样能保证程序具有一定的启发性，使搜索树分支最少。

模板

【模板】舞蹈链（DLX）

模板代码 
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register ll
#define il inline
const int N = 500 + 10;
int n, m, idx, ans;
int first[N], siz[N], stk[N];
struct DLXNODE {
  int lc, rc, up, dn, r, c;
};
il int read() {
  rgi x = 0, f = 0, ch;
  while(!isdigit(ch = getchar())) f |= ch == '-';
  while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
struct DLX {
  static const int MAXSIZE = 1e5 + 10;
#define IT(i, A, x) for(i = A[x]; i != x; i = A[i])
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];
  void build(const int &r, const int &c) {
    n = r, m = c;
    for(rgi 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;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }
  void insert(const int &r, const 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(!first[r]) first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }
  void remove(const int &c) {
    rgi i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    IT(i, D, c) IT(j, R, i)
    U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }
  void recover(const int &c) {
    rgi i, j;
    IT(i, U, c) IT(j, L, i)
    U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }
  bool dance(int dep) {
    if(!R[0]) { ans = dep; return 1; }
    rgi i, j, c = R[0];
    IT(i, R, 0) if(siz[i] < siz[c]) c = i;
    remove(c);
    IT(i, D, c) {
      stk[dep] = row[i];
      IT(j, R, i) remove(col[j]);
      if(dance(dep + 1)) return 1;
      IT(j, L, i) recover(col[j]);
    }
    recover(c);
    return 0;
  }
#undef IT
} solver;
int main() {
  n = read(), m = read();
  solver.build(n, m);
  for(rgi i = 1; i <= n; ++i) for(rgi j = 1; j <= m; ++j) {
    int x = read();
    if(x) solver.insert(i, j);
  } solver.dance(1);
  if(ans)
    for(rgi i = 1; i < ans; ++i) printf("%d ", stk[i]);
  else
    puts("No Solution!");
  return 0;
}

时间复杂度分析

DLX 的时间复杂度是 指数级 的，它递归及回溯的次数与矩阵中 1 的个数有关，与矩阵的 r, c 等参数无关。

因此理论复杂度大概在 O(c^n) 左右，其中 c 为某个非常接近于 1 的常数， n 为矩阵中 1 的个数。

但实际情况下 DLX 表现良好，一般能解决大部分的问题。

如何建模

DLX 的难点，不全在于链表的建立，而在于建模。

请确保已经完全掌握 DLX 模板后再继续阅读本文。

我们每拿到一个题，应该考虑行和列所表示的意义：

  • 行表示决策，因为每行对应着一个集合，也就对应着选/不选；

  • 列表示状态，因为第 i 列对应着某个条件 P_i 。

对于某一行而言，由于不同的列的值不尽相同，我们 由不同的状态，定义了一个决策 。

  1. 数独

    解题思路

    先考虑决策是什么。

    在这一题中，每一个决策可以用形如 (r, c, w) 的有序三元组表示。

    注意到 “宫” 并不是决策的参数，因为它 可以被每个确定的 (r, c) 表示。

    因此有 9 \times 9 \times 9 = 729 行。

    再考虑状态是什么。

    我们思考一下 (r, c, w) 这个决将会造成什么影响。记 (r, c) 所在的宫为 b 。

    (1) 第 r 行用了一个 w （用 9 \times 9 = 81 列表示）；

    (2) 第 c 列用了一个 w （用 9 \times 9 = 81 列表示）；

    (3) 第 b 宫用了一个 w （用 9 \times 9 = 81 列表示）；

    (4) (r, c) 中填入了一个数（用 9 \times 9 = 81 列表示）。

    因此有 81 \times 4 = 324 列，共 729 \times 4 = 2916 个 1 。

    至此，我们成功地将 9 \times 9 的数独问题转化成了一个有 729 行， 324 列，共 2916 个 1 的精确覆盖问题。

    参考代码 
    #include <bits/stdc++.h>
#define LL long long
#define rgi register int
#define il inline
const int N = 1e6 + 10;
#define JUDGE 0
#define DEBUG 0
int ans[10][10], stk[N];
il int read() {
  rgi x = 0, f = 0, ch;
  while(!isdigit(ch = getchar())) f |= ch == '-';
  while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
struct DLX {
  static const int MAXSIZE = 1e5 + 10;
#define IT(i, A, x) for(i = A[x]; i != x; i = A[i])
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];
  void build(const int &r, const int &c) {
    n = r, m = c;
    for(rgi 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;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }
  void insert(const int &r, const 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(!first[r]) first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }
  void remove(const int &c) {
    rgi i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    IT(i, D, c) IT(j, R, i)
    U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }
  void recover(const int &c) {
    rgi i, j;
    IT(i, U, c) IT(j, L, i)
    U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }
  bool dance(int dep) {
    rgi i, j, c = R[0];
    if(!R[0]) {
      for(i = 1; i < dep; ++i) {
        int x = (stk[i] - 1) / 9 / 9 + 1;
        int y = (stk[i] - 1) / 9 % 9 + 1;
        int v = (stk[i] - 1) % 9 + 1;
        ans[x][y] = v;
      }
      return 1;
    }
    IT(i, R, 0) if(siz[i] < siz[c]) c = i;
    remove(c);
    IT(i, D, c) {
      stk[dep] = row[i];
      IT(j, R, i) remove(col[j]);
      if(dance(dep + 1)) return 1;
      IT(j, L, i) recover(col[j]);
    }
    recover(c);
    return 0;
  }
} solver;
int GetId(int row, int col, int num) { return (row - 1) * 9 * 9 + (col - 1) * 9 + num; }
void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1;
  int dy = (col - 1) / 3 + 1;
  int room = (dx - 1) * 3 + dy;
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num; // task 1
  int f2 = 81 + (col - 1) * 9 + num; // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num; // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col; // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}
int main() {
#if JUDGE
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
#endif
  solver.build(729, 324);
  for(rgi i = 1; i <= 9; ++i) for(rgi j = 1; j <= 9; ++j) {
    ans[i][j] = read();
    for(rgi v = 1; v <= 9; ++v) {
      if(ans[i][j] && ans[i][j] != v) continue;
      Insert(i, j, v);
    }
  } solver.dance(1);
  for(rgi i = 1; i <= 9; ++i, putchar('\n')) for(rgi j = 1; j <= 9; ++j, putchar(' '))
    printf("%d", ans[i][j]);
  return 0;
}

  2. 靶形数独

    解题思路

    这一题与 数独 的模型构建 一模一样，主要区别在于答案的更新。

    这一题可以开一个权值数组，每次找到一组数独的解时，

    每个位置上的数乘上对应的权值计入答案即可。

    参考代码 
    #include <bits/stdc++.h>
#define LL long long
#define il inline
const int oo = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int e[] = { 6, 6, 6, 6, 6, 6, 6, 6, 6,
                  6, 7, 7, 7, 7, 7, 7, 7, 6,
                  6, 7, 8, 8, 8, 8, 8, 7, 6,
                  6, 7, 8, 9, 9, 9, 8, 7, 6,
                  6, 7, 8, 9, 10, 9, 8, 7, 6,
                  6, 7, 8, 9, 9, 9, 8, 7, 6,
                  6, 7, 8, 8, 8, 8, 8, 7, 6,
                  6, 7, 7, 7, 7, 7, 7, 7, 6,
                  6, 6, 6, 6, 6, 6, 6, 6, 6
                };
int ans = -oo, a[10][10], stk[N];
il int read() {
  int x = 0, f = 0, ch;
  while(!isdigit(ch = getchar())) f |= ch == '-';
  while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
int GetWeight(int row, int col, int num) { return num * e[(row - 1) * 9 + (col - 1)]; }
struct DLX {
  static const int MAXSIZE = 1e5 + 10;
#define IT(i, A, x) for(i = A[x]; i != x; i = A[i])
  int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10];
  int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZE + 10], D[MAXSIZE + 10];
  int col[MAXSIZE + 10], row[MAXSIZE + 10];
  void build(const int &r, const int &c) {
    n = r, m = c;
    for(int 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;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }
  void insert(const int &r, const 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(!first[r]) first[r] = L[tot] = R[tot] = tot;
    else {
      R[tot] = R[first[r]], L[R[first[r]]] = tot;
      L[tot] = first[r], R[first[r]] = tot;
    }
  }
  void remove(const int &c) {
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    IT(i, D, c) IT(j, R, i)
    U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }
  void recover(const int &c) {
    int i, j;
    IT(i, U, c) IT(j, L, i)
    U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }
  void dance(int dep) {
    int i, j, c = R[0];
    if(!R[0]) {
      int cur_ans = 0;
      for(i = 1; i < dep; ++i) {
        int cur_row = (stk[i] - 1) / 9 / 9 + 1;
        int cur_col = (stk[i] - 1) / 9 % 9 + 1;
        int cur_num = (stk[i] - 1) % 9 + 1;
        cur_ans += GetWeight(cur_row, cur_col, cur_num);
      }
      ans = std::max(ans, cur_ans);
      return;
    }
    IT(i, R, 0) if(siz[i] < siz[c]) c = i;
    remove(c);
    IT(i, D, c) {
      stk[dep] = row[i];
      IT(j, R, i) remove(col[j]);
      dance(dep + 1);
      IT(j, L, i) recover(col[j]);
    }
    recover(c);
  }
} solver;
int GetId(int row, int col, int num) { return (row - 1) * 9 * 9 + (col - 1) * 9 + num; }
void Insert(int row, int col, int num) {
  int dx = (row - 1) / 3 + 1; // r
  int dy = (col - 1) / 3 + 1; // c
  int room = (dx - 1) * 3 + dy; // room
  int id = GetId(row, col, num);
  int f1 = (row - 1) * 9 + num; // task 1
  int f2 = 81 + (col - 1) * 9 + num; // task 2
  int f3 = 81 * 2 + (room - 1) * 9 + num; // task 3
  int f4 = 81 * 3 + (row - 1) * 9 + col; // task 4
  solver.insert(id, f1);
  solver.insert(id, f2);
  solver.insert(id, f3);
  solver.insert(id, f4);
}
int main() {
  solver.build(729, 324);
  for(int i = 1; i <= 9; ++i) for(int j = 1; j <= 9; ++j) {
    a[i][j] = read();
    for(int v = 1; v <= 9; ++v) {
      if(a[i][j] && v != a[i][j]) continue;
      Insert(i, j, v);
    }
  } solver.dance(1);
  printf("%d", ans == -oo ? -1 : ans);
  return 0;
}

  3. 「NOI2005」智慧珠游戏

    解题思路

    定义：题中给我们的智慧珠的形态，称为这个智慧珠的 标准形态。

    显然，我们可以通过改变两个参数 d （表示顺时针旋转 90^{\circ} 的次数）和 f （是否水平翻转）来改变这个智慧珠的形态。

    仍然，我们先考虑决策是什么。

    在这一题中，每一个决策可以用形如 (v, d, f, i) 的有序五元组表示。

    表示第 i 个智慧珠的 标准形态 的左上角的位置，序号为 v ，经过了 d 次顺时针转 90^{\circ} 。

    巧合的是，我们可以令 f = 1 时不水平翻转， f = -1 时水平翻转，从而达到简化代码的目的。

    因此有 55 \times 4 \times 2 \times 12 = 5280 行。

    需要注意的是，因为一些不合法的填充，如 (1, 0, 1, 4) ，

    所以在实际操作中，空的智慧珠棋盘也只需要建出 2730 行。

    再考虑状态是什么。

    这一题的状态比较简单。

    我们思考一下， (v, d, f, i) 这个决策会造成什么影响。

    (1) 某些格子被占了（用 55 列表示）；

    (2) 第 i 个智慧珠被用了（用 12 列表示）。

    因此有 55 + 12 = 67 列，共 5280 \times (5 + 1) = 31680 个 1 。

    至此，我们成功地将智慧珠游戏转化成了一个有 5280 行， 67 列，共 31680 个 1 的精确覆盖问题。

    参考代码 
    #include <bits/stdc++.h>
#define LL long long
int numcol, numrow;
int dfn[3000], tx[2], nxt[2], num[50][50], vis[50];
char ans[50][50];
const int f[2] = { -1, 1 };
const int table[12][5][2] = {
  // directions of shapes
  { { 0, 0 }, { 1, 0 }, { 0, 1 } },                       // A
  { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 } },             // B
  { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 } },             // C
  { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 } },             // D
  { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, 1 }, { 2, 2 } },   // E
  { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 0, 2 }, { 0, 3 } },   // F
  { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } },   // G
  { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 }, { 0, 2 } },   // H
  { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 3 } },   // I
  { { 0, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 0, 2 } },  // J
  { { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 }, { 2, 2 } },   // K
  { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 } },   // L
};
const int len[12] = { 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5 };
const int getx[] = { 0,  1,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  6,  6,
                     6,  7,  7,  7,  7,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,
                     9,  9,  9,  9,  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11,
                     11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13,
                     13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14
                   };
const int gety[] = { 0,  1, 1, 2,  1, 2, 3, 1, 2, 3, 4,  1,  2,  3,  4,  5, 1, 2, 3, 4, 5, 6, 1, 2, 3,  4,
                     5,  6, 7, 1,  2, 3, 4, 5, 6, 7, 8,  1,  2,  3,  4,  5, 6, 7, 8, 9, 1, 2, 3, 4, 5,  6,
                     7,  8, 9, 10, 1, 2, 3, 4, 5, 6, 7,  8,  9,  10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
                     12, 1, 2, 3,  4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1,  2, 3, 4, 5, 6, 7, 8, 9
                   };
struct DLX {
  static const int MS = 1e5 + 10;
#define IT(i, A, x) for (i = A[x]; i != x; i = A[i])
  int n, m, tot, first[MS], siz[MS];
  int L[MS], R[MS], U[MS], D[MS];
  int col[MS], row[MS];
  void build(const int &r, const int &c) {
    n = r, m = c;
    for (rgi 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;
    memset(first, 0, sizeof(first));
    memset(siz, 0, sizeof(siz));
  }
  void insert(const int &r, const 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 (!first[r])
      first[r] = L[tot] = R[tot] = tot;
    else
      R[tot] = R[first[r]], L[R[first[r]]] = tot, L[tot] = first[r], R[first[r]] = tot;  // !
  }
  void remove(const int &c) {
    rgi i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    IT(i, D, c) IT(j, R, i) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  }
  void recover(const int &c) {
    rgi i, j;
    IT(i, U, c) IT(j, L, i) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
    L[R[c]] = R[L[c]] = c;
  }
  bool dance() {
    if (!R[0])
      return 1;
    rgi i, j, c = R[0];
    IT(i, R, 0) if (siz[i] < siz[c]) c = i;
    remove(c);
    IT(i, D, c) {
      if (col[i] <= 55)
        ans[getx[col[i]]][gety[col[i]]] = dfn[row[i]] + 'A';
      IT(j, R, i) {
        remove(col[j]);
        if (col[j] <= 55)
          ans[getx[col[j]]][gety[col[j]]] = dfn[row[j]] + 'A';
      }
      if (dance())
        return 1;
      IT(j, L, i) recover(col[j]);
    }
    recover(c);
    return 0;
  }
#undef IT
} solver;
int main() {
  for (rgi i = 1; i <= 10; ++i) scanf("%s", ans[i] + 1);
  for (rgi i = 1; i <= 10; ++i)
    for (rgi j = 1; j <= i; ++j) {
      if (ans[i][j] != '.')
        vis[ans[i][j] - 'A'] = 1;
      num[i][j] = ++numcol;
    }
  solver.build(2730, numcol + 12);
  /*******build*******/
  for (rgi id = 0, op; id < 12; ++id) {  // every block
    for (++numcol, op = 0; op <= 1; ++op) {
      for (rgi dx = 0; dx <= 1; ++dx) {
        for (rgi dy = 0; dy <= 1; ++dy) {
          for (tx[0] = 1; tx[0] <= 10; ++tx[0]) {
            for (tx[1] = 1; tx[1] <= tx[0]; ++tx[1]) {
              bool flag = 1;
              for (rgi k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                if (vis[id]) {
                  if (ans[nxt[0]][nxt[1]] != id + 'A') {
                    flag = 0;
                    break;
                  }
                } else if (ans[nxt[0]][nxt[1]] != '.') {
                  flag = 0;
                  break;
                }
              }
              if (!flag)
                continue;
              dfn[++numrow] = id;
              solver.insert(numrow, numcol);
              for (rgi k = 0; k < len[id]; ++k) {
                nxt[op] = tx[op] + f[dx] * table[id][k][0];
                nxt[op ^ 1] = tx[op ^ 1] + f[dy] * table[id][k][1];
                solver.insert(numrow, num[nxt[0]][nxt[1]]);
              }
            }
          }
        }
      }
    }
  }
  /********end********/
  if (!solver.dance())
    puts("No solution");
  else
    for (rgi i = 1; i <= 10; ++i, puts(""))
      for (rgi j = 1; j <= i; ++j) putchar(ans[i][j]);
  return 0;
}

练习

  1. SUDOKU - Sudoku
  2. 「kuangbin 带你飞」专题三 Dancing Links

总结

DLX 能用来解决精确覆盖问题，适当地建立起模型后能解决一些大模拟。

References

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article LeverImmy
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments