这是一种奇妙的算法用来解决两个问题：
- 精确覆盖问题：给定一个矩阵，每行是一个二进制数，选出尽量少的行，使得每一列恰好有一个 \(1\)
- 重复覆盖问题：给定一个矩阵，每行是一个二进制数，选出尽量少的行，使得每列至少有一个 \(1\)。
模板一般需要有两个：① 数据结构（十字链表）② dfs 框架
其中 ① 对于两个问题都是一样的，而 ② 不同问题不同框架。
精确覆盖问题
1. 如何存储这个矩阵：十字链表
由于 \(0\) 的信息冗余，我们只存 \(1\)，不存 \(0\)，复杂度可以做到和 \(1\) 的个数相关，这样就处理掉了那种稀疏图（行列很大，但 \(1\) 的个数很少的情况）。
十字链表 QWQ
对于所有 \(1\) 的位置建立节点。
看一下每个节点上下左右应该连向谁，这里十字链表是一个循环链表。举个例子，如果 \((x, y)\) 上面没有节点，那么循环到最底下，然后再往上走，直到走到第一个 \(1\)。
实际到代码实现，我们可以按行创建：
- 预备信息
const int N = 具体问题中 1 最多的点数。
int n, m, U[N], D[N], L[N], R[N], idx, s[N], hh, tt, X[N], Y[N];
/*
n 为行数，m 为列数，U/D/L/R[i] 分别表示 i 节点上下左右的节点。
idx 为当前用了的点数, s[i] 表示第 i 列为 1 的有多少行。
hh, tt 用于加入点时两个端点。
X[i], Y[i] 表示 i 号点的 x, y 坐标
*/
- 首先第一行是哨兵（全 \(1\)），并且 \((0, 0)\) 加入一个节点以便后续快速找到现在还有多少个 \(1\)。
void inline init() {
for (int i = 0; i <= m; i++)
L[i] = i - 1, R[i] = i + 1, U[i] = D[i] = i;
L[0] = m, R[m] = 0, idx = m;
}
- 每一次加入一行。然后考虑左右两个点 \(hh, tt\)，每次动态把一个 \(1\) 插入到 \(hh, tt\) 之间。
void inline add(int x, int y) {
X[++idx] = x, Y[idx] = y, s[y]++;
L[idx] = hh, R[idx] = tt, L[tt] = R[hh] = idx;
U[idx] = U[y], D[idx] = y, D[U[y]] = idx, U[y] = idx;
// 注意 U[y] = idx 必须在最后，因为其他东西需要用到之前的 U[y]，即 idx 上面那个店。
hh = idx;
}
// 读入 n * m 的矩阵并按行加入
for (int i = 1; i <= n; i++) {
hh = idx + 1, tt = idx + 1; // 可以理解为第一行第一个点左右都是自己。
for (int j = 1, x; j <= m; j++) {
scanf("%d", &x);
if (x) add(i, j); // 如果 i, j 为 1，加入 (i, j)
}
}
按行插入有趣的是，你只需要把它搞成一个循环链表就行了，甚至你随便左右的顺序也是可以过的，只要保持在同一行循环链表的性质就可以。
for (int i = 1; i <= n; i++) {
hh = idx + 1, tt = idx + 1;
len = 0;
for (int j = 1, x; j <= m; j++) {
scanf("%d", &x);
if (x) d[++len] = j;
}
random_shuffle(d + 1, d + 1 + len); // 233
for (int j = 1; j <= len; j++) add(i, d[j]);
}
QAQ
- 删除第 \(p\) 列及其关联的所有行。删除列的时候，只需要删除第一行对应的列，原因在于我们 dfs 时找是通过第一行的哨兵找；删除行的时候，只需要把行对应列的位置删掉（这列的 \(s\) 信息就不管了，反正以后也不用了），行相互作用是不需要删的，原因是不影响，且我们需要用行的信息恢复现场.jpg
void del(int p) {
L[R[p]] = L[p], R[L[p]] = R[p];
for (int i = D[p]; i != p; i = D[i]) {
for (int j = R[i]; j != i; j = R[j]) {
s[Y[j]]--, U[D[j]] = U[j], D[U[j]] = D[j];
}
}
}
- 按插入顺序撤销第 \(p\) 列，注意这里按照时间逆序操作即可，相互不影响的时间顺序可以改变。
void resume(int p) {
L[R[p]] = p, R[L[p]] = p;
for (int i = U[p]; i != p; i = U[i]) {
for (int j = L[i]; j != i; j = L[j]) {
s[Y[j]]++, U[D[j]] = j, D[U[j]] = j;
}
}
}
2. dfs 框架：针对精确覆盖问题。
每次任意选择未被选择的一行，判断能不能选。
剪枝：
- 挑 \(1\) 的个数最少的列。枚举这一列选哪个行。如果我们选择了这一列，接下来就不需要考虑这一列的影响了，所以我们可以把这一列删掉（十字链表的操作）。
- 选择一行，实际上是把这行所有 \(1\) 的列都选了，即删掉这些列，然后这些列关系到的行也都没了，把这些行也干掉，禁止套娃。有些人可能认为这会造成无休止的删，但实际上只会影响两次，为什么能，即选择一行 \(\Rightarrow\) 删掉对应列 \(\Rightarrow\) 废掉对应列的行，废掉和选择是不一样的，废掉就不会影响其他列了。
经过这两步，我们可以理解为，\(dfs\) 到当前的数据结构上都是没选的列和行，相当于每次选一行把问题转化成了更小规模，即选择一行，把与这行冲突的行删掉，并且删掉对应列，通过十字链表，我们做到了快速删除/查找。
bool inline dfs() {
if (!R[0]) return true;
int p = R[0];
for (int i = R[0]; i; i = R[i])
if (s[i] < s[p]) p = i;
if (!s[p]) return false;
del(p);
for (int i = D[p]; i != p; i = D[i]) {
ans[++top] = X[i];
for (int j = R[i]; j != i; j = R[j]) del(Y[j]);
if (dfs()) return true;
for (int j = L[i]; j != i; j = L[j]) resume(Y[j]);
--top;
}
resume(p);
return false;
}
时间复杂度
约为 \(O(c ^ n)\)，其中 \(c\) 是一个接近 \(1\) 的常数，\(n\) 为矩阵中 \(1\) 的个数。随机数据的话 \(n\) 到上万级别也没啥问题。（又是一个玄学复杂度的算法）。
例题
题目 \(\Rightarrow\) 模型的转化，可以把每一个决策当成一行，限制当成一列，如果一个限制恰好一次那么就可以精确覆盖。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5505, M = 505;
int n, m, U[N], D[N], L[N], R[N], idx, s[N], hh, tt, X[N], Y[N];
int ans[M], top;
void inline init() {
for (int i = 0; i <= m; i++)
L[i] = i - 1, R[i] = i + 1, U[i] = D[i] = i;
L[0] = m, R[m] = 0, idx = m;
}
void inline add(int x, int y) {
X[++idx] = x, Y[idx] = y, s[y]++;
L[idx] = hh, R[idx] = tt, L[tt] = R[hh] = idx;
U[idx] = U[y], D[idx] = y, D[U[y]] = idx, U[y] = idx;
hh = idx;
}
// 删除第 p 列
void del(int p) {
L[R[p]] = L[p], R[L[p]] = R[p];
for (int i = D[p]; i != p; i = D[i]) {
for (int j = R[i]; j != i; j = R[j]) {
s[Y[j]]--, U[D[j]] = U[j], D[U[j]] = D[j];
}
}
}
void resume(int p) {
L[R[p]] = p, R[L[p]] = p;
for (int i = U[p]; i != p; i = U[i]) {
for (int j = L[i]; j != i; j = L[j]) {
s[Y[j]]++, U[D[j]] = j, D[U[j]] = j;
}
}
}
bool inline dfs() {
if (!R[0]) return true;
int p = R[0];
for (int i = R[0]; i; i = R[i])
if (s[i] < s[p]) p = i;
if (!s[p]) return false;
del(p);
for (int i = D[p]; i != p; i = D[i]) {
ans[++top] = X[i];
for (int j = R[i]; j != i; j = R[j]) del(Y[j]);
if (dfs()) return true;
for (int j = L[i]; j != i; j = L[j]) resume(Y[j]);
--top;
}
resume(p);
return false;
}
int main() {
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++) {
hh = idx + 1, tt = idx + 1;
for (int j = 1, x; j <= m; j++) {
scanf("%d", &x);
if (x) add(i, j);
}
}
if (!dfs()) puts("No Solution!");
else for (int i = 1; i <= top; i++) printf("%d ", ans[i]);
return 0;
}
行数：设空出的格子有 \(n\) 个，那么每个格子可以填 \(16\) 个字母，共 \(n * 16\) 行（决策）。
列数：即限制，每个格子恰好一个数字 \(n+\) 每行每列每个十六宫格每个数都出现恰好一次 \(3n\) \(= 4n\)
每行恰好 \(4\) 个 \(1\)，即格子的位置 \(1\)，行列十六宫格位置 \(1\)。
这样总点数是 \(n \times 64 \le 16384\) 个格子，这题暴力强剪枝可过，所以 Dacing Links 显然也能过。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 17, S = 4, P = 16385, M = N * N * N;
int n, m, U[P], D[P], L[P], R[P], X[P], Y[P], s[P];
int idx, ans[M], top, tot, hh, tt;
// 各自限制的状态编号
bool st[N];
char a[N][N];
struct Selection{
int x, y;
char c;
} e[M];
void inline clear() {
n = idx = tot = top = 0, m = 1024;
memset(s, 0, sizeof s);
}
void init() {
for (int i = 0; i <= m; i++)
L[i] = i - 1, R[i] = i + 1, U[i] = D[i] = i;
L[0] = m, R[m] = 0, idx = m;
}
void inline add(int x, int y) {
X[++idx] = x, Y[idx] = y, s[y]++;
L[idx] = hh, R[idx] = tt, R[hh] = L[tt] = idx;
U[idx] = U[y], D[idx] = y, D[U[y]] = idx, U[y] = idx;
tt = idx;
}
void del(int p) {
L[R[p]] = L[p], R[L[p]] = R[p];
for (int i = U[p]; i != p; i = U[i]) {
for (int j = R[i]; j != i; j = R[j]) {
s[Y[j]]--, D[U[j]] = D[j], U[D[j]] = U[j];
}
}
}
void resume(int p) {
L[R[p]] = p, R[L[p]] = p;
for (int i = D[p]; i != p; i = D[i]) {
for (int j = L[i]; j != i; j = L[j]) {
s[Y[j]]++, D[U[j]] = j, U[D[j]] = j;
}
}
}
bool dfs() {
if (!R[0]) return true;
int p = R[0];
for (int i = R[0]; i; i = R[i])
if (s[i] < s[p]) p = i;
if (!s[p]) return false;
del(p);
for (int i = U[p]; i != p; i = U[i]) {
ans[++top] = X[i];
for (int j = R[i]; j != i; j = R[j]) del(Y[j]);
if (dfs()) return true;
for (int j = L[i]; j != i; j = L[j]) resume(Y[j]);
top--;
}
resume(p);
return false;
}
int main() {
while (~scanf("%s", a[0])) {
clear();
for (int i = 1; i <= 15; i++) scanf("%s", a[i]);
// 把限制总状态数抠出来
init();
for (int i = 0; i < 16; i++) {
for (int j = 0; j < 16; j++) {
int l = 0, r = 15;
if (a[i][j] != '-') l = r = a[i][j] - 'A';
for (int k = l; k <= r; k++) {
hh = idx + 1, tt = idx + 1;
e[++n] = (Selection) { i, j, (char)(k + 'A') } ;
add(n, (j + 1) + i * 16), add(n, 16 * 16 + i * 16 + k + 1);
add(n, 16 * 32 + j * 16 + k + 1), add(n, 16 * 48 + (i / 4 * 4 + j / 4) * 16 + k + 1);
}
}
}
dfs();
for (int i = 1; i <= top; i++)
a[e[ans[i]].x][e[ans[i]].y] = e[ans[i]].c;
for (int i = 0; i < 16; i++) printf("%s\n", a[i]);
puts("");
}
return 0;
}
重复覆盖问题
基本搜索框架：IDA*，层数不能太多）
跟精确覆盖问题的区别就是，考虑选择一行，只会把它关联的所有列删掉，并不会套娃删行，这是因为同一列下 \(1\) 的行同时选并不冲突。
但这样会慢很多，需要加一个 IDA*。
估价函数是：
- 枚举没选的列，选上所有的行，股价函数 \(+1\)
这种方法可以看作把这列的所有行并起来算成一个行了，这个东西经过大量经验表明整挺快。
注意，这里删的时候是把对应列在在那些行里删掉。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10005, M = 505;
int n, m, U[N], D[N], L[N], R[N], idx, s[N], hh, tt, X[N], Y[N];
int ans[M], top, dep, d[M];
bool st[N];
void inline init() {
for (int i = 0; i <= m; i++)
L[i] = i - 1, R[i] = i + 1, U[i] = D[i] = i;
L[0] = m, R[m] = 0, idx = m;
}
void inline add(int x, int y) {
X[++idx] = x, Y[idx] = y, s[y]++;
L[idx] = hh, R[idx] = tt, L[tt] = R[hh] = idx;
U[idx] = U[y], D[idx] = y, D[U[y]] = idx, U[y] = idx;
hh = idx;
}
// 删除第 p 列
void inline del(int p) {
for (int i = D[p]; i != p; i = D[i])
L[R[i]] = L[i], R[L[i]] = R[i];
}
void resume(int p) {
for (int i = U[p]; i != p; i = U[i])
L[R[i]] = i, R[L[i]] = i;
}
int inline h() {
memset(st, false, sizeof st);
int cnt = 0;
for (int i = R[0]; i; i = R[i]) {
if (st[i]) continue;
cnt++;
for (int j = D[i]; j != i; j = D[j])
for (int k = R[j]; k != j; k = R[k]) st[Y[k]] = true;
}
return cnt;
}
bool inline dfs() {
if (top + h() > dep) return false;
if (!R[0]) return true;
int p = R[0];
for (int i = R[0]; i; i = R[i])
if (s[i] < s[p]) p = i;
if (!s[p]) return false;
for (int i = D[p]; i != p; i = D[i]) {
ans[++top] = X[i];
del(i);
for (int j = R[i]; j != i; j = R[j]) del(j);
if (dfs()) return true;
for (int j = L[i]; j != i; j = L[j]) resume(j);
resume(i);
--top;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++) {
hh = idx + 1, tt = idx + 1;
for (int j = 1, x; j <= m; j++) {
scanf("%d", &x);
if (x) add(i, j);
}
}
dep = 1;
while(!dfs()) dep++;
printf("%d\n", dep);
for (int i = 1; i <= dep; i++) printf("%d ", ans[i]);
return 0;
}