关于精确覆盖问题

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

精确覆盖问题描述起来十分简洁：

给定一个全集 UU 和若干集合 S1,S2,S3,…,SnS_{1},S_{2},S_{3},\ldots ,S_{n} ，现需从中选取某些集合，不重不漏地覆盖全集 UU

或者可以用 0-1 矩阵来表示：

UU 1 2 3 4 5 6 7
S1S_{1} 0 1 0 0 0 1 0
S2S_{2} 0 0 0 1 1 1 0
S3S_{3} 0 1 1 0 0 0 1
S4S_{4} 1 0 0 1 0 0 1
S5S_{5} 1 0 0 1 0 0 0
S6S_{6} 0 0 1 0 1 0 1

答案是 S1S_{1}、S5S_{5} 和 S6S_{6} ，你看看是不是

这种问题的通用解法是 X 算法，我稍微简化了一下过程：

首先按大小顺序依次选取每一行，目前来说也就是第一行 S1S_{1}

（有个剪枝优化是依次选元素最少列上的非零行，搜索会更快）

UU 1 2 3 4 5 6 7
S1 0 1 0 0 0 1 0
S2S_{2} 0 0 0 1 1 1 0
S3S_{3} 0 1 1 0 0 0 1
S4S_{4} 1 0 0 1 0 0 1
S5S_{5} 1 0 0 1 0 0 0
S6S_{6} 0 0 1 0 1 0 1

然后找到非空元素的所在列

UU 1 2 3 4 5 6 7
S1 0 1 0 0 0 1 0
S2S_{2} 0 0 0 1 1 1 0
S3S_{3} 0 1 1 0 0 0 1
S4S_{4} 1 0 0 1 0 0 1
S5S_{5} 1 0 0 1 0 0 0
S6S_{6} 0 0 1 0 1 0 1

然后再顺藤摸瓜地选中目前所有非空元素所在的行

UU 1 2 3 4 5 6 7
S1 0 1 0 0 0 1 0
S2 0 0 0 1 1 1 0
S3 0 1 1 0 0 0 1
S4S_{4} 1 0 0 1 0 0 1
S5S_{5} 1 0 0 1 0 0 0
S6S_{6} 0 0 1 0 1 0 1

现在把选中的部分全部删掉，生成一个新矩阵

UU 1 3 4 5 7
S4S_{4} 1 0 1 0 1
S5S_{5} 1 0 1 0 0
S6S_{6} 0 1 0 1 1

再选取第一行 S4S_{4}

UU 1 3 4 5 7
S4 1 0 1 0 1
S5S_{5} 1 0 1 0 0
S6S_{6} 0 1 0 1 1

重复上面的操作

UU 1 3 4 5 7
S4 1 0 1 0 1
S5 1 0 1 0 0
S6 0 1 0 1 1

然后发现删完所有行后 3 和 5 并没有覆盖到，所以这不是一个解

UU 3 5

回溯，这次选取第二行，也就是 S5S_{5}

UU 1 3 4 5 7
S4S_{4} 1 0 1 0 1
S5 1 0 1 0 0
S6S_{6} 0 1 0 1 1

再重复算法

UU 1 3 4 5 7
S4 1 0 1 0 1
S5 1 0 1 0 0
S6S_{6} 0 1 0 1 1

现在来看就已经很简单了

UU 3 5 7
S6S_{6} 1 1 1

最后再选中 S6S_{6} 即可

UU 3 5 7
S6 1 1 1

全部删完了，得到了一个解

UU

还记得前面删除的是哪些行嘛？分别是 S1S_{1}、S5S_{5} 和 S6S_{6} ，这就是 X 算法

舞蹈链（Dancing Links）简介

现在要写一个程序实现 X 算法 ，但是有一个问题，就是没有合适的数据结构

如果使用二维数组的话，删除行和列，缓存和回溯状态都十分难以实现，而且复杂度堪忧

算法大师 Donald Knuth 为此提出了 Dancing Links（舞蹈链），它是一种链式数据结构，利用链表的性质解决了上述难题。由于删除、恢复等操作是指针之间的跳跃，仿佛是精妙的舞蹈一般，由此得名

而使用 Dancing Links 数据结构的 X 算法 就被成为 Dancing Links X 算法

舞蹈链结构，每行每列都是环形链接，每个结点都有四方向的指针

但是这个图我感觉有点问题，就是行首结点貌似是不在环里的，而且只有向右的指针

分步讲解

整体结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct DLX
{
    int n, m, id;               // 行数，列数，最大结点的编号（包含总表头、列首结点和元素结点，行首结点是另外单独存的）
    int U[N], D[N], L[N], R[N]; // 第i个结点的上下左右结点编号
    int Row[N], Col[N];         // 第i个结点的行号，列号
    int firstNodePerRow[N];     // 行首结点，指向第i行的第一个元素结点
    int nodeNumPerCol[N];       // 第i列的元素结点数目，后面用于剪枝优化
    int ans[N];                 // 保存解，ans[0]表示总行数，后面依次为结果

    void init(int n, int m);    // 初始化，建立n行m列的DLX矩阵
    void add(int x, int y);     // 在x行y列插入元素结点
    void remove(int c);         // 删除列c及其牵扯到的行（其实是隐藏，访问不到就行）
    void resume(int c);         // 恢复列c及其牵扯到的行
    bool dance(int deepth);     // 递归搜索
    void print();               // 打印解
}

（本来还想写些东西的，但是我感觉我已经有很多注释了）

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 初始化，建立n行m列的DLX矩阵
void init(int n, int m)
{
    this->n = n; // 行数
    this->m = m; // 列数
    id = m;      // 0是总表头，1~m是列首结点，m+1开始是真实的元素结点

    // 写入初始状态数据
    for (int i = 0; i <= m; i++)
    {
        U[i] = D[i] = i; // 列首结点的上下指针指向自己
        L[i] = i - 1;    // 列首结点的左指针指向前一个列首结点
        R[i] = i + 1;    // 列首结点的右指针指向后一个列首结点
    }

    // 为方便遍历，让列首成环
    L[0] = m; // 总表头的左指针指向最后一个列首结点
    R[m] = 0; // 最后一个列首结点的右指针指向总表头

    memset(nodeNumPerCol, 0, sizeof(nodeNumPerCol));
    memset(firstNodePerRow, 0, sizeof(firstNodePerRow));
}

这里再强调一下，行首结点不算真的结点，所以初始化的时候是 id = m; 而不是 id = n + m;

加入结点

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
// 在x行y列插入元素结点
void add(int x, int y)
{
    id++;               // 新结点的编号
    Row[id] = x;        // 记录行号
    Col[id] = y;        // 记录列号
    nodeNumPerCol[y]++; // 第y列的元素结点数目+1

    // 在列首结点y的下方插入新结点（不用关心元素顺序，都能遍历到就行）
    U[id] = y;    // 新结点的上指针指向列首结点
    D[id] = D[y]; // 新结点的下指针指向列首结点的原下方结点
    U[D[y]] = id; // 列首结点的原下方结点的上指针指向新结点
    D[y] = id;    // 列首结点的下指针指向新结点

    // 在行首结点x的右方插入新结点
    if (firstNodePerRow[x] == 0) // 如果本行还没有元素结点
    {
        firstNodePerRow[x] = id; // 让行首结点指向自己
        L[id] = R[id] = id;      // 新结点的左右指针指向自己
    }
    else // 如果本行已经有元素结点
    {
        L[id] = firstNodePerRow[x];    // 新结点的左指针指向行首结点
        R[id] = R[firstNodePerRow[x]]; // 新结点的右指针指向行首结点的原右方结点
        L[R[firstNodePerRow[x]]] = id; // 行首结点的原右方结点的左指针指向新结点
        R[firstNodePerRow[x]] = id;    // 行首结点的右指针指向新结点
    }

    return; // 如果你细心的话，会发现每一行，每一列的结点都是成环的（不包括行首结点）
}

如果你忘记了链表的操作建议复习一下，简单来说就是先搞清楚要插入的位置，让前面结点认为它后面是我，然后让后面结点认为它前面是我

删除列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 删除列c及其牵扯到的行（其实是隐藏，访问不到就行）
void remove(int c)
{
    L[R[c]] = L[c]; // 列首结点的右方结点的左指针指向列首结点的左方结点
    R[L[c]] = R[c]; // 列首结点的左方结点的右指针指向列首结点的右方结点

    // 遍历列c的所有元素结点，因为是成环的，所以终止条件是遍历到自己
    for (int i = D[c]; i != c; i = D[i])
    {
        // 遍历每个元素所在的行并删除结点，因为是成环的，所以终止条件是遍历到自己
        for (int j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = U[j];          // 元素结点的下方结点的上指针指向元素结点的上方结点
            D[U[j]] = D[j];          // 元素结点的上方结点的下指针指向元素结点的下方结点
            nodeNumPerCol[Col[j]]--; // 第Col[j]列的元素结点数目-1
        }
    }

    return;
}

恢复列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 恢复列c及其牵扯到的行
void resume(int c)
{
    // 遍历列c的所有元素结点
    for (int i = U[c]; i != c; i = U[i])
    {
        // 遍历每个元素所在的行并恢复结点
        for (int j = L[i]; j != i; j = L[j])
        {
            U[D[j]] = j;             // 元素结点的下方结点的上指针指向元素结点
            D[U[j]] = j;             // 元素结点的上方结点的下指针指向元素结点
            nodeNumPerCol[Col[j]]++; // 第Col[j]列的元素结点数目+1
        }
    }

    L[R[c]] = c; // 列首结点的右方结点的左指针指向列首结点
    R[L[c]] = c; // 列首结点的左方结点的右指针指向列首结点

    return; // 不得不说，这个结构设计的是真的精巧
}

因为删除的时候只是让左右访问不到该列，但是直接使用下标还是可以访问的，所以是可以恢复的

开始跳舞！

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
// 递归搜索
bool dance(int deepth)
{
    if (R[0] == 0) // 矩阵已经删除完，得到一个解
    {
        ans[0] = deepth - 1;
        return true;
    }

    // 每次选择一个元素结点数目最少的列并删除，这是一个优化
    int c = R[0];
    for (int i = R[0]; i != 0; i = R[i])
    {
        if (nodeNumPerCol[i] < nodeNumPerCol[c])
            c = i;
    }
    remove(c);

    // 遍历列c的所有元素结点，并依次尝试删除所在的行
    for (int i = D[c]; i != c; i = D[i])
    {
        ans[deepth] = Row[i]; // 删除之前先标记为答案

        for (int j = R[i]; j != i; j = R[j])
            remove(Col[j]); // 删除列Col[j]及其牵扯到的行

        if (dance(deepth + 1)) // 递归
            return true;

        for (int j = L[i]; j != i; j = L[j])
            resume(Col[j]); // 恢复列Col[j]及其牵扯到的行
    }

    resume(c); // 恢复列c及其牵扯到的行
    return false;
}

这里就是使用了我前面说的剪枝优化，使用选择结点数最少的列依次删除

打印解

1
2
3
4
5
6
7
8
9
10
11
12
void print()
{
    if (ans[0] == 0)
    {
        printf("No solution!\n");
        return;
    }

    for (int i = 1; i <= ans[0]; i++)
        printf("%d ", ans[i]);
    printf("\n");
}

这应该就比较好理解了

完整代码

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

struct DLX
{
    int n, m, id;               // 行数，列数，最大结点的编号（包含总表头、列首结点和元素结点，行首结点是另外单独存的）
    int U[N], D[N], L[N], R[N]; // 第i个结点的上下左右结点编号
    int Row[N], Col[N];         // 第i个结点的行号，列号
    int firstNodePerRow[N];     // 行首结点，指向第i行的第一个元素结点
    int nodeNumPerCol[N];       // 第i列的元素结点数目
    int ans[N];                 // 保存解，ans[0]表示总行数，后面依次为结果

    // 初始化，建立n行m列的DLX矩阵
    void init(int n, int m)
    {
        this->n = n; // 行数
        this->m = m; // 列数
        id = m;      // 0是总表头，1~m是列首结点，m+1开始是真实的元素结点

        // 写入初始状态数据
        for (int i = 0; i <= m; i++)
        {
            U[i] = D[i] = i; // 列首结点的上下指针指向自己
            L[i] = i - 1;    // 列首结点的左指针指向前一个列首结点
            R[i] = i + 1;    // 列首结点的右指针指向后一个列首结点
        }

        // 为方便遍历，让列首成环
        L[0] = m; // 总表头的左指针指向最后一个列首结点
        R[m] = 0; // 最后一个列首结点的右指针指向总表头

        memset(nodeNumPerCol, 0, sizeof(nodeNumPerCol));
        memset(firstNodePerRow, 0, sizeof(firstNodePerRow));
    }

    // 在x行y列插入元素结点
    void add(int x, int y)
    {
        id++;               // 新结点的编号
        Row[id] = x;        // 记录行号
        Col[id] = y;        // 记录列号
        nodeNumPerCol[y]++; // 第y列的元素结点数目+1

        // 在列首结点y的下方插入新结点（不用关心元素顺序，都能遍历到就行）
        U[id] = y;    // 新结点的上指针指向列首结点
        D[id] = D[y]; // 新结点的下指针指向列首结点的原下方结点
        U[D[y]] = id; // 列首结点的原下方结点的上指针指向新结点
        D[y] = id;    // 列首结点的下指针指向新结点

        // 在行首结点x的右方插入新结点
        if (firstNodePerRow[x] == 0) // 如果本行还没有元素结点
        {
            firstNodePerRow[x] = id; // 让行首结点指向自己
            L[id] = R[id] = id;      // 新结点的左右指针指向自己
        }
        else // 如果本行已经有元素结点
        {
            L[id] = firstNodePerRow[x];    // 新结点的左指针指向行首结点
            R[id] = R[firstNodePerRow[x]]; // 新结点的右指针指向行首结点的原右方结点
            L[R[firstNodePerRow[x]]] = id; // 行首结点的原右方结点的左指针指向新结点
            R[firstNodePerRow[x]] = id;    // 行首结点的右指针指向新结点
        }

        return; // 如果你细心的话，会发现每一行，每一列的结点都是成环的（不包括行首结点）
    }

    // 删除列c及其牵扯到的行（其实是隐藏，访问不到就行）
    void remove(int c)
    {
        L[R[c]] = L[c]; // 列首结点的右方结点的左指针指向列首结点的左方结点
        R[L[c]] = R[c]; // 列首结点的左方结点的右指针指向列首结点的右方结点

        // 遍历列c的所有元素结点，因为是成环的，所以终止条件是遍历到自己
        for (int i = D[c]; i != c; i = D[i])
        {
            // 遍历每个元素所在的行并删除结点，因为是成环的，所以终止条件是遍历到自己
            for (int j = R[i]; j != i; j = R[j])
            {
                U[D[j]] = U[j];          // 元素结点的下方结点的上指针指向元素结点的上方结点
                D[U[j]] = D[j];          // 元素结点的上方结点的下指针指向元素结点的下方结点
                nodeNumPerCol[Col[j]]--; // 第Col[j]列的元素结点数目-1
            }
        }

        return;
    }

    // 恢复列c及其牵扯到的行
    void resume(int c)
    {
        // 遍历列c的所有元素结点
        for (int i = U[c]; i != c; i = U[i])
        {
            // 遍历每个元素所在的行并恢复结点
            for (int j = L[i]; j != i; j = L[j])
            {
                U[D[j]] = j;             // 元素结点的下方结点的上指针指向元素结点
                D[U[j]] = j;             // 元素结点的上方结点的下指针指向元素结点
                nodeNumPerCol[Col[j]]++; // 第Col[j]列的元素结点数目+1
            }
        }

        L[R[c]] = c; // 列首结点的右方结点的左指针指向列首结点
        R[L[c]] = c; // 列首结点的左方结点的右指针指向列首结点

        return; // 不得不说，这个结构设计的是真的精巧
    }

    // 递归搜索
    bool dance(int deepth)
    {
        if (R[0] == 0) // 矩阵已经删除完，得到一个解
        {
            ans[0] = deepth - 1;
            return true;
        }

        // 每次选择一个元素结点数目最少的列并删除，这是一个优化
        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i])
        {
            if (nodeNumPerCol[i] < nodeNumPerCol[c])
                c = i;
        }
        remove(c);

        // 遍历列c的所有元素结点，并依次尝试删除所在的行
        for (int i = D[c]; i != c; i = D[i])
        {
            ans[deepth] = Row[i]; // 删除之前先标记为答案

            for (int j = R[i]; j != i; j = R[j])
                remove(Col[j]); // 删除列Col[j]及其牵扯到的行

            if (dance(deepth + 1)) // 递归
                return true;

            for (int j = L[i]; j != i; j = L[j])
                resume(Col[j]); // 恢复列Col[j]及其牵扯到的行
        }

        resume(c); // 恢复列c及其牵扯到的行
        return false;
    }

    void print()
    {
        if (ans[0] == 0)
        {
            printf("No solution!\n");
            return;
        }

        for (int i = 1; i <= ans[0]; i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
} dlx;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n = read(), m = read();
    dlx.init(n, m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (read())
                dlx.add(i, j);
        }
    dlx.dance(1);
    dlx.print();
}

举一反三

解决 N 皇后问题

P1219 [USACO1.5]八皇后 Checker Challenge

N 皇后的棋盘有 n∗nn*n 个点，并且有四种条件

  1. 每行只能放一个皇后（ nn 行）
  2. 每列只能放一个皇后（ nn 列）
  3. 每一个“/”斜行只能放一个皇后（ 2∗n−12*n-1 个对角线）
  4. 每一个“\”斜行只能放一个皇后（ 又是 2∗n−12*n-1 个对角线）

将每个点作为行（共 n∗nn*n 行），将每个条件作为列（共 6∗n−26*n-2 列）

列的存储空间分配：

  • [1,n][1,n] ：棋盘行
  • [n+1,2∗n][n+1,2*n] ：棋盘列
  • [2∗n+1,4∗n−1][2*n+1,4*n-1] ：主对角线
  • [4∗n,6∗n−2][4*n,6*n-2] ：次对角线

然后结束条件为填满前 nn 列即可，并且删除的列必须在前 nn 列中

解决数独问题

P1784 数独

也是一样的，只是条件变成了格、行、列、宫

要开 9∗99*9 行，然后把每种条件展开铺到列上

参考资料

这两位都是真大佬，我真的自愧不如（

哪里没讲清楚或者有错的地方建议赶快踢我