舞蹈链（DLX） 笔记

一、精确覆盖问题 & 重复覆盖问题

以下部分例子来自 OI-Wiki。

形式化的语言：有若干个集合 $S_{1\dots n}$，给定一个集合 $T$，要求给出一种方案 $p_{1\dots m}$，满足：

• $\bigcap _{i=1}^m{S}_{p_i}=\text{empty}$；
• $\bigcup _{i=1}^n{S}_{p_i}=T$

感性理解：选择若干个集合，使得选择的不同集合内没有相同的元素，且选择的集合的所有元素恰好就是给定集合 $T$ 内的所有元素。

例如，若给出

$$\begin{array}{rl}& 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{array}$$

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

二、X 算法

将每个 $S$ 是否存在某个元素表示为一个二进制数，一行一行表示出来：

$$\left(\begin{array}{cccccccc}& 1& 3& 5& 8& 9& 17& 119\\ S_1& 0& 0& 1& 0& 1& 1& 0\\ S_2& 1& 0& 0& 1& 0& 0& 1\\ S_3& 0& 1& 1& 0& 0& 1& 0\\ S_4& 1& 0& 0& 1& 0& 0& 0\\ S_5& 0& 1& 0& 0& 0& 0& 1\\ S_6& 0& 0& 0& 1& 1& 0& 1\end{array}\right)$$

问题转换为选择若干行，使得每一列恰好有一个 $1$。

X 算法的流程如下：先选择一行，通过标记这一行 $1$ 所在的列，把和这一行有相同位置 $1$ 的行全部删去，得到新的小矩阵后继续操作，如果最后删掉了一个全为 $1$ 的行后矩阵变为空，则方案可行，否则回溯。

如上例：

1. 选择第一行，删去红色的行（和第一行有相同的 $1$ 位置）和蓝色的列（无需继续考虑）。

$$\begin{gathered} \left(\begin{array}{ccccccc}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{array}\right) \\ \downarrow \\ \left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right) \end{gathered}$$

2. 选择新矩阵第一行（即原矩阵第二行）。

$$\begin{gathered} \left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right) \\ \downarrow \\ \left(\begin{array}{}\end{array}\right) \end{gathered}$$

3. 此时发现第二步选择的行并非全为 $1$，说明存在列未被覆盖，回溯，选择第二行（即原矩阵第四行）。

$$\begin{gathered} \left(\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right) \\ \downarrow \\ \left(\begin{array}{cc}1& 1\end{array}\right) \end{gathered}$$

4. 此时删掉这剩下的一行（原矩阵第五行），矩阵全空且删除合法，故求出答案 $(S_1,S_4,S_5)$。

三、双向十字链表

其实，可以理解为链式前向星 Pro Max。

双向十字链表有四个指针 $U,D,L,R$，分别指向四个方向，但其并不是按照行列编号顺序指向的，他是像链式前向星一样，head 指向最新的，最新的指向第二新的，……

此外，它的指针是循环的，也就是说如果向左跳，到了左边界，再往左跳他会跳回右边界，这使得双向十字链表实质上不需要 head，可以从任意位置开始遍历，遍历回自己后结束。

首先，假设需要一个大小为 $r\times c$ 的双向十字链表，$0$ 号点用来判断矩阵是否全空，创建一条链 $1\to c$ 的链，相当于向下方向的 head，而行方向就单独开一个 head 数组即可。

若 $(1,2)$ 加入一个点，标号为 $5$，就把 $D_2$ 指向这个点。

若 $(3,2)$ 加入一个点，标号为 $5$，就把 $D_2$ 指向这个点，$D_6$ 指向 $5$，因为 $D$ 实质上起的是链式前向星的功能而不是按行号向下指的功能。

若 $(3,4)$ 加入一个点，在行方向和加入 $(3,2)$ 时进行类似的操作即可。

至于 $U$ 和 $L$，由于和 $D,R$ 分别互逆，按图理解即可，不再赘述。

int r, c, head[N], sz[N], idx;
int X[N], Y[N], L[N], R[N], U[N], D[N];
void build(int n, int m) {
    r = n, c = m;
    for (int i = 0; i <= c; i++) {
        L[i] = i - 1, R[i] = i + 1;
        U[i] = D[i] = i;
    }
    idx = c;
    L[0] = c, R[c] = 0;
    memset(head, 0, sizeof head);
    memset(sz, 0, sizeof sz);
}
void insert(int x, int y) {
    X[++idx] = x, Y[idx] = y, sz[y]++;
    U[idx] = y, D[idx] = D[y];
    U[D[y]] = idx, D[y] = idx;
    if (!head[x])
        head[x] = L[idx] = R[idx] = idx;
    else {
        L[idx] = head[x], R[idx] = R[head[x]];
        L[R[head[x]]] = idx, R[head[x]] = idx;
    }
}

四、舞蹈链

对于 X 算法的矩阵，可以只对 $1$ 建立一个双向十字链表。

1. 精确覆盖问题

写一个 remove 函数，表示删除某一列上有 $1$ 位置的所有行。每次选择 $1$ 最少的一列，枚举选择这一列的哪些行，选择之后再删除和这一行有冲突的不能被选的行。

为什么选择 $1$ 最少的一列？因为有 $1$ 的列上总有一行会成为正解，否则说明无法覆盖掉这一列，而选择 $1$ 最少的一列显然可以加快速度。

删除完之后复原即可，如果最后删空了返回可行。

为什么删空了即可？按照代码，如果某一列出现了 $1$，那么它向下方向的 head 也会被删掉，如果每一列都出现过 $1$ 了，那么链表显然是完全空的 head 都没了，所以不需要特殊判断最后删除的是否全为 $1$。

如果无法理解代码里的细节，记住双向十字链表是循环的，不会掉出界的，而 $1\to c$ 的编号是分给了一些类似 head 的点的。

void remove(int y) {
    L[R[y]] = L[y], R[L[y]] = R[y];
    for (int i = D[y]; i != y; i = D[i])
        for (int j = R[i]; j != i; j = R[j]) {
            U[D[j]] = U[j],
            D[U[j]] = D[j];
            sz[Y[j]]--;
        }
}
void recover(int y) {
    for (int i = U[y]; i != y; i = U[i])
        for (int j = L[i]; j != i; j = L[j]) {
            U[D[j]] = D[U[j]] = j;
            sz[Y[j]]++;
        }
    L[R[y]] = R[L[y]] = y;
}
bool dance(int step) {
    if (!R[0]) {
        cnt = step;
        return true;
    }
    int y = R[0];
    for (int i = R[0]; i; i = R[i])
        if (sz[i] < sz[y])
            y = i;
    remove(y);
    for (int i = D[y]; i != y; i = D[i]) {
        ans[step + 1] = X[i];
        for (int j = R[i]; j != i; j = R[j])
            remove(Y[j]);
        if (dance(step + 1))
            return true;
        for (int j = L[i]; j != i; j = L[j])
            recover(Y[j]);
    }
    recover(y);
    return false;
}

2. 重复覆盖问题

不能删除掉和某一行有冲突的行了，虽然还是可以删掉某一行所有的 $1$ 出现的列，但是效率将大幅下降，故写一个估价函数，估价函数的内容是，我们假定覆盖某一列的所有行，他们覆盖的列都只需要一个集合就能覆盖完，这样子显然估出来的步数是小的，但这也说明了如果往小的估都不合法，那肯定不能合法。

重复覆盖问题通常询问最小覆盖集合数，套一个迭代加深即可。

void remove(int x) {
    for (int i = D[x]; i != x; i = D[i])
        L[R[i]] = L[i], R[L[i]] = R[i];
}
void recover(int x) {
    for (int i = U[x]; i != x; i = U[i])
        L[R[i]] = R[L[i]] = i;
}
int h() {
    int ret = 0;
    memset(vis, 0, sizeof vis);
    for (int i = R[0]; i; i = R[i]) {
        if (vis[i])
            continue;
        vis[i] = true;
        ret++;
        for (int j = D[i]; j != i; j = D[j])
            for (int k = R[j]; k != j; k = R[k])
                vis[Y[k]] = true;
    }
    return ret;
}
bool dance(int step) {
    if (step + h() > mxd)
        return false;
    if (!R[0])
        return true;
    int y = R[0];
    for (int i = R[0]; i; i = R[i])
        if (sz[i] < sz[y])
            y = i;
    for (int i = D[y]; i != y; i = D[i]) {
        ans[step + 1] = X[i];
        remove(i);
        for (int j = R[i]; j != i; j = R[j])
            remove(j);
        if (dance(step + 1))
            return true;
        for (int j = L[i]; j != i; j = L[j])
            recover(j);
        recover(i);
    }
    return false;
}
void solve() {
    mxd = 0;
    while (!dance(0))
        mxd++;
    cout << mxd << "\n";
}

五、刷题套路

这玩意最常用来解决数独类问题，理解了一个就可以理解全部了。

假设当前要解决九行九列数独问题，有行，列，宫的限制，把决策放到行，影响放到列。

如决策在数独第 $x$ 行第 $y$ 列放入 $z$，那么会影响到这个位置不能再放别的数，第 $x$ 行不能再放 $z$，第 $y$ 列不能再放 $z$，所在宫不能再放 $z$。

每一个格子是否放数；每一行，每一列，每一宫是否放 $1\sim 9$，共有 $9\times 9\times 4$ 种情况，每一个格子放 $1\sim 9$，共有 $9^3$ 种决策，故只需要一个 $729\times 324$ 的双向十字链表做精确覆盖问题即可。

几道题：

• P1784 数独。
• P4205 [NOI2005] 智慧珠游戏。
• UVA1603 破坏正方形 Square Destroyer。