精确覆盖问题

精确覆盖问题

精确覆盖问题(Exact Cover Problem),指给定许多集合$S_i\left(1\le i\le n\right)$,
以及集合$X\subset S$,求满足以下条件的无序多元组$\left(T_1,T_2,\cdots ,T_m\right)$:

1. $\forall i,j\in \left[1,m\right],T_i\cap T_j=\varnothing \left(i\ne j\right)$
2. $X={\cup }_{i=1}^m{T}_i$
3. ∀ i ∈ [ 1 , m ] , T i ∈ { S 1 , ⋯   , S n } \forall i\in \left[1,m\right],T_i\in\left\{S_1,\cdots,S_n\right\} ∀i∈[1,m],Ti​∈{S1​,⋯,Sn​}

问题转化

( 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 ) \left(

\right) ⎝ ⎛​010100​001010​101000​010101​100001​101000​010011​⎠ ⎞​
行代表每一个集合，列代表每一个元素
那问题就转化为选择某几行，使得满足那些条件
如果暴力枚举，假设$m$行$n$列，时间复杂度$O\left(nm\cdot 2^n\right)$

X算法

其实和暴力没啥差别，就是枚举的时候删除对应行和对应列
比如选了第1行，则第3行和第6行就不能选了，进而转化为
( 1 0 1 1 1 0 1 0 0 1 0 1 ) \left(

\right) ⎝ ⎛​110​001​110​101​⎠ ⎞​

舞蹈链

舞蹈链(Dancing Links)，其实就是X算法，用十字链表

十字链表定义

const int MAXN = 5505, M = 505, N = 505;
int left[MAXN], right[MAXN], up[MAXN], down[MAXN];//每个元素上下左右
int row[MAXN], col[MAXN];//每一个元素所在行和列
int head[M+5], col_size[N+5], cnt = 0;//每行第一个元素，每列元素个数，总元素个数
1
2
3
4

下面图均来自OI WIKI

记住下标从1开始，因为0相当于一个头

初始化

初始化需要初始化成这样

void init(const int& N) {
	for (int i = 0; i <= N; ++i) {
		left[i] = i - 1;
		right[i] = i + 1;
		up[i] = down[i] = i;
	}
	left[0] = N;
	right[N] = 0;
	memset(head, -1, sizeof(head));
	memset(col_size, 0, sizeof(col_size));
	cnt = N + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

插入元素

相对于列来说，这其实就是头插法，然后维护双向链表
对于行来说，就是插到head[r]的左边

记住下标从1开始

void link(const int& r, const int& c) {
	++col_size[c];
	row[cnt] = r;
	col[cnt] = c;
	up[cnt] = c;
	down[cnt] = down[c];
	up[down[c]] = cnt;
	down[c] = cnt;
	if (head[r] == -1) {
		head[r] = left[cnt] = right[cnt] = cnt;
	}
	else {
		right[cnt] = head[r];
		left[cnt] = left[head[r]];
		right[left[head[r]]] = cnt;
		left[head[r]] = cnt;
	}

	++cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除

删除c列，以及相关的行

先删除列，然后从上往下遍历，删除行

void remove(const int& c) {
	right[left[c]] = right[c];
	left[right[c]] = left[c];
	for (int i = down[c]; i != c; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = up[j];
			down[up[j]] = down[j];
			--col_size[col[j]];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

恢复

反着跑一遍删除

void resume(const int& c) {
	for (int i = up[c]; i != c; i = up[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = j;
			down[up[j]] = j;
			++col_size[col[j]];
		}
	}
	right[left[c]] = c;
	left[right[c]] = c;
}
1
2
3
4
5
6
7
8
9
10
11

主程序

选择1最少的列，删除
遍历这一列，枚举是否选择这一行

这里注意恢复的时候一定要left

bool dance(int dep) {
	if (right[0] == 0) {
		return true;
	}
	int c = right[0];
	for (int i = right[c]; i != 0; i = right[i]) {
		if (col_size[i] < col_size[c]) {
			c = i;
		}
	}
	remove(c);
	for (int i = down[c]; i != c; i = down[i]) {
		ans_row[ans++] = row[i];
		for (int j = right[i]; j != i; j = right[j]) {
			remove(col[j]);
		}
		if (dance(dep + 1)) {
			return true;
		}
		for (int j = left[i]; j != i; j = left[j]) {
			resume(col[j]);
		}
		--ans;
	}
	resume(c);
	return false;
}
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

完整

#include
#include

const int MAXN = 5505, M = 505, N = 505;
int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
int row[MAXN], col[MAXN], head[M+5], col_size[N+5], cnt = 0;
int ans, ans_row[M];

void init(const int& N) {
	for (int i = 0; i <= N; ++i) {
		left[i] = i - 1;
		right[i] = i + 1;
		up[i] = down[i] = i;
	}
	left[0] = N;
	right[N] = 0;
	memset(head, -1, sizeof(head));
	memset(col_size, 0, sizeof(col_size));
	cnt = N + 1;
}
void link(const int& r, const int& c) {
	++col_size[c];
	row[cnt] = r;
	col[cnt] = c;
	up[cnt] = c;
	down[cnt] = down[c];
	up[down[c]] = cnt;
	down[c] = cnt;
	if (head[r] == -1) {
		head[r] = left[cnt] = right[cnt] = cnt;
	}
	else {
		right[cnt] = head[r];
		left[cnt] = left[head[r]];
		right[left[head[r]]] = cnt;
		left[head[r]] = cnt;
	}

	++cnt;
}

void remove(const int& c) {
	right[left[c]] = right[c];
	left[right[c]] = left[c];
	for (int i = down[c]; i != c; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = up[j];
			down[up[j]] = down[j];
			--col_size[col[j]];
		}
	}
}
void resume(const int& c) {
	for (int i = up[c]; i != c; i = up[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = j;
			down[up[j]] = j;
			++col_size[col[j]];
		}
	}
	right[left[c]] = c;
	left[right[c]] = c;
}

bool dance(int dep) {
	if (right[0] == 0) {
		return true;
	}
	int c = right[0];
	for (int i = right[c]; i != 0; i = right[i]) {
		if (col_size[i] < col_size[c]) {
			c = i;
		}
	}
	remove(c);
	for (int i = down[c]; i != c; i = down[i]) {
		ans_row[ans++] = row[i];
		for (int j = right[i]; j != i; j = right[j]) {
			remove(col[j]);
		}
		if (dance(dep + 1)) {
			return true;
		}
		for (int j = left[i]; j != i; j = left[j]) {
			resume(col[j]);
		}
		--ans;
	}
	resume(c);
	return false;
}
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

类版本

#include
#include

const int M = 505, N = 505;
class DLX {
public:
	static const int MAXN = 5505;
	int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
	int row[MAXN], col[MAXN], head[M+5], col_size[N+5], cnt;
	int ans, ans_row[M];
	DLX() :cnt(0), ans(0) {}
	void init(const int& N) {
		cnt = ans = 0;
		for (int i = 0; i <= N; ++i) {
			left[i] = i - 1;
			right[i] = i + 1;
			up[i] = down[i] = i;
		}
		left[0] = N;
		right[N] = 0;
		memset(head, -1, sizeof(head));
		memset(col_size, 0, sizeof(col_size));
		cnt = N + 1;
	}
	void link(const int& r, const int& c) {
		++col_size[c];
		row[cnt] = r;
		col[cnt] = c;
		up[cnt] = c;
		down[cnt] = down[c];
		up[down[c]] = cnt;
		down[c] = cnt;
		if (head[r] == -1) {
			head[r] = left[cnt] = right[cnt] = cnt;
		}
		else {
			right[cnt] = head[r];
			left[cnt] = left[head[r]];
			right[left[head[r]]] = cnt;
			left[head[r]] = cnt;
		}

		++cnt;
	}
	void remove(const int& c) {
		right[left[c]] = right[c];
		left[right[c]] = left[c];
		for (int i = down[c]; i != c; i = down[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = up[j];
				down[up[j]] = down[j];
				--col_size[col[j]];
			}
		}
	}
	void resume(const int& c) {
		for (int i = up[c]; i != c; i = up[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = j;
				down[up[j]] = j;
				++col_size[col[j]];
			}
		}
		right[left[c]] = c;
		left[right[c]] = c;
	}
	bool dance(int dep) {
		if (right[0] == 0) {
			return true;
		}
		int c = right[0];
		for (int i = right[c]; i != 0; i = right[i]) {
			if (col_size[i] < col_size[c]) {
				c = i;
			}
		}
		remove(c);
		for (int i = down[c]; i != c; i = down[i]) {
			ans_row[ans++] = row[i];
			for (int j = right[i]; j != i; j = right[j]) {
				remove(col[j]);
			}
			if (dance(dep + 1)) {
				return true;
			}
			for (int j = left[i]; j != i; j = left[j]) {
				resume(col[j]);
			}
			--ans;
		}
		resume(c);
		return false;
	}
};
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

洛谷P4929

https://www.luogu.com.cn/problem/P4929

#include
#include

const int M = 505, N = 505;
class DLX {
public:
	static const int MAXN = 5505;
	int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
	int row[MAXN], col[MAXN], head[M+5], col_size[N+5], cnt;
	int ans, ans_row[M];
	DLX() :cnt(0), ans(0) {}
	void init(const int& N) {
		cnt = ans = 0;
		for (int i = 0; i <= N; ++i) {
			left[i] = i - 1;
			right[i] = i + 1;
			up[i] = down[i] = i;
		}
		left[0] = N;
		right[N] = 0;
		memset(head, -1, sizeof(head));
		memset(col_size, 0, sizeof(col_size));
		cnt = N + 1;
	}
	void link(const int& r, const int& c) {
		++col_size[c];
		row[cnt] = r;
		col[cnt] = c;
		up[cnt] = c;
		down[cnt] = down[c];
		up[down[c]] = cnt;
		down[c] = cnt;
		if (head[r] == -1) {
			head[r] = left[cnt] = right[cnt] = cnt;
		}
		else {
			right[cnt] = head[r];
			left[cnt] = left[head[r]];
			right[left[head[r]]] = cnt;
			left[head[r]] = cnt;
		}

		++cnt;
	}
	void remove(const int& c) {
		right[left[c]] = right[c];
		left[right[c]] = left[c];
		for (int i = down[c]; i != c; i = down[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = up[j];
				down[up[j]] = down[j];
				--col_size[col[j]];
			}
		}
	}
	void resume(const int& c) {
		for (int i = up[c]; i != c; i = up[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = j;
				down[up[j]] = j;
				++col_size[col[j]];
			}
		}
		right[left[c]] = c;
		left[right[c]] = c;
	}
	bool dance(int dep) {
		if (right[0] == 0) {
			return true;
		}
		int c = right[0];
		for (int i = right[c]; i != 0; i = right[i]) {
			if (col_size[i] < col_size[c]) {
				c = i;
			}
		}
		remove(c);
		for (int i = down[c]; i != c; i = down[i]) {
			ans_row[ans++] = row[i];
			for (int j = right[i]; j != i; j = right[j]) {
				remove(col[j]);
			}
			if (dance(dep + 1)) {
				return true;
			}
			for (int j = left[i]; j != i; j = left[j]) {
				resume(col[j]);
			}
			--ans;
		}
		resume(c);
		return false;
	}
};
int main() {
	DLX solver;
	int m, n;
	scanf("%d%d", &m, &n);
	solver.init(n);
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			int t;
			scanf("%d", &t);
			if (t == 1) {
				solver.link(i, j);
			}
		}
	}
	if (solver.dance(0)) {
		for (int i = 0; i < solver.ans; ++i) {
			if (i > 0) {
				printf(" ");
			}
			printf("%d", solver.ans_row[i]);
		}
		printf("\n");
	}
	else {
		printf("No Solution!\n");
	}
	return 0;
}
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

洛谷P1784

https://www.luogu.com.cn/problem/P1784

行：81个格子，有9个数字，所以需要729个
列：$\left[81\ast 0+1,81\right]$用来记录这个数字填在了哪
$\left[81\ast 1+1,81\ast 2\right]$用来记录行的1-9
$\left[81\ast 2+1,81\ast 3\right]$用来记录列的1-9
$\left[81\ast 3+1,81\ast 4\right]$用来记录九宫格的1-9
总共需要324个

然后插入就是每一个格子枚举，如果这个格子已经填过了，那就不需要枚举

MAXN理论上开到$729\ast 4+324+1+1$就够了

#include
#include

const int H = 9;
const int M = H * H * H, N = H * H * 4;
class DLX {
public:
	static const int MAXN = M * 4 + N + 5;
	int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
	int row[MAXN], col[MAXN], head[MAXN], col_size[MAXN], cnt;
	int ans, ans_row[H*H];
	DLX() :cnt(0), ans(0) {}
	void init(const int& N) {
		cnt = ans = 0;
		for (int i = 0; i <= N; ++i) {
			left[i] = i - 1;
			right[i] = i + 1;
			up[i] = down[i] = i;
		}
		left[0] = N;
		right[N] = 0;
		memset(head, -1, sizeof(head));
		memset(col_size, 0, sizeof(col_size));
		cnt = N + 1;
	}
	void link(const int& r, const int& c) {
		++col_size[c];
		row[cnt] = r;
		col[cnt] = c;
		up[cnt] = c;
		down[cnt] = down[c];
		up[down[c]] = cnt;
		down[c] = cnt;
		if (head[r] == -1) {
			head[r] = left[cnt] = right[cnt] = cnt;
		}
		else {
			right[cnt] = head[r];
			left[cnt] = left[head[r]];
			right[left[head[r]]] = cnt;
			left[head[r]] = cnt;
		}

		++cnt;
	}
	void remove(const int& c) {
		right[left[c]] = right[c];
		left[right[c]] = left[c];
		for (int i = down[c]; i != c; i = down[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = up[j];
				down[up[j]] = down[j];
				--col_size[col[j]];
			}
		}
	}
	void resume(const int& c) {
		for (int i = up[c]; i != c; i = up[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = j;
				down[up[j]] = j;
				++col_size[col[j]];
			}
		}
		right[left[c]] = c;
		left[right[c]] = c;
	}
	bool dance(int dep) {
		if (right[0] == 0) {
			return true;
		}
		int c = right[0];
		for (int i = right[c]; i != 0; i = right[i]) {
			if (col_size[i] < col_size[c]) {
				c = i;
			}
		}
		remove(c);
		for (int i = down[c]; i != c; i = down[i]) {
			ans_row[ans++] = row[i];
			for (int j = right[i]; j != i; j = right[j]) {
				remove(col[j]);
			}
			if (dance(dep + 1)) {
				return true;
			}
			for (int j = left[i]; j != i; j = left[j]) {
				resume(col[j]);
			}
			--ans;
		}
		resume(c);
		return false;
	}
};
int main() {
	DLX solver;
	solver.init(N);
	int a[H][H];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < H; ++j) {
			scanf("%d", &a[i][j]);
			for (int k = 1; k <= H; ++k) {
				if (a[i][j] == 0 || a[i][j] == k) {
					int idx = i * H * H + j * H + k;
					solver.link(idx, i * H + j + 1);
					solver.link(idx, H * H + i * H + k);
					solver.link(idx, H * H * 2 + j * H + k);
					solver.link(idx, H * H * 3 + (i / 3 * 3 + j / 3) * 9 + k);
				}
			}
		}
	}
	if (solver.dance(0)) {
		for (int i = 0; i < solver.ans; ++i) {
			int cur = solver.ans_row[i];
			int r = (cur - 1) / (H*H), c = (cur - 1) / H % H, k = (cur - 1) % 9 + 1;
			a[r][c] = k;
		}
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < H; ++j) {
				if (j > 0)printf(" ");
				printf("%d", a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}
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

洛谷P1219

https://www.luogu.com.cn/problem/P1219

与上一题类似
行：$n\ast n$个格子
列：$\left[1,n\right]$用来记录这个数字填在了哪行
$\left[n+1,2n\right]$用来记录这个数字填在了哪列
$\left[2n+1,4n-1\right]$用来记录这个数字填在了哪条副对角线(从$(0,0)$开始)
$\left[4n,6n-2\right]$用来记录这个数字填在了哪条主对角线(从$(n-1,0)$开始)

但是注意一点，对角线是无法完全覆盖的
比如下面的图，第3条副对角线就没有覆盖

所以如果行和列覆盖完了就可以返回了

#include
#include
#include

const int H = 13;
const int M = H * H, N = 6 * H - 2;
int n, board_cnt;
struct A {
	int a[H];
}board[100000];
bool cmp(const A& a, const A& b) {
	int i = 0;
	while (i < n && a.a[i] == b.a[i])++i;
	return a.a[i] < b.a[i];
};
class DLX {
public:
	static const int MAXN = M * 4 + N + 5;
	int left[MAXN], right[MAXN], up[MAXN], down[MAXN];
	int row[MAXN], col[MAXN], head[M+5], col_size[N+5], cnt;
	int ans, ans_row[H];
	DLX() :cnt(0), ans(0) {}
	void init(const int& N) {
		cnt = ans = 0;
		for (int i = 0; i <= N; ++i) {
			left[i] = i - 1;
			right[i] = i + 1;
			up[i] = down[i] = i;
		}
		left[0] = N;
		right[N] = 0;
		memset(head, -1, sizeof(head));
		memset(col_size, 0, sizeof(col_size));
		cnt = N + 1;
	}
	void link(const int& r, const int& c) {
		++col_size[c];
		row[cnt] = r;
		col[cnt] = c;
		up[cnt] = c;
		down[cnt] = down[c];
		up[down[c]] = cnt;
		down[c] = cnt;
		if (head[r] == -1) {
			head[r] = left[cnt] = right[cnt] = cnt;
		}
		else {
			right[cnt] = head[r];
			left[cnt] = left[head[r]];
			right[left[head[r]]] = cnt;
			left[head[r]] = cnt;
		}

		++cnt;
	}
	void remove(const int& c) {
		right[left[c]] = right[c];
		left[right[c]] = left[c];
		for (int i = down[c]; i != c; i = down[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = up[j];
				down[up[j]] = down[j];
				--col_size[col[j]];
			}
		}
	}
	void resume(const int& c) {
		for (int i = up[c]; i != c; i = up[i]) {
			for (int j = right[i]; j != i; j = right[j]) {
				up[down[j]] = j;
				down[up[j]] = j;
				++col_size[col[j]];
			}
		}
		right[left[c]] = c;
		left[right[c]] = c;
	}
	void dance(int dep) {
		if (right[0]>n) {
			for (int i = 0; i < n; ++i) {
				int x = (ans_row[i] - 1) / n;
				int y = (ans_row[i] - 1) % n + 1;
				board[board_cnt].a[x] = y;
			}
			++board_cnt;
			return;
		}
		int c = right[0];
		for (int i = right[c]; i != 0 && i <= n; i = right[i]) {
			if (col_size[i] < col_size[c]) {
				c = i;
			}
		}
		remove(c);
		for (int i = down[c]; i != c; i = down[i]) {
			ans_row[ans++] = row[i];
			for (int j = right[i]; j != i; j = right[j]) {
				remove(col[j]);
			}
			dance(dep + 1);
			for (int j = left[i]; j != i; j = left[j]) {
				resume(col[j]);
			}
			--ans;
		}
		resume(c);
		return;
	}
};
int main() {
	scanf("%d", &n);
	DLX solver;
	solver.init(6 * n - 2);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int idx = i * n + j + 1;
			solver.link(idx, i + 1);
			solver.link(idx, n + j + 1);
			solver.link(idx, 2 * n + 1 + i + j);
			solver.link(idx, 4 * n + n + j - i - 1);
		}
	}
	solver.dance(0);
	std::sort(board, board + board_cnt, cmp);
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < n; ++j) {
			if (j > 0)printf(" ");
			printf("%d", board[i].a[j]);
		}
		printf("\n");
	}
	printf("%d\n", board_cnt);
	return 0;
}
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

参考：
https://oi-wiki.org/search/dlx/