洛谷 P4929 【模板】舞蹈链（DLX） 精确匹配

缘起

【1】中讲解了DLX算法的思想, 这里肯定要拿道题目来把DLX的模板写出来啊~

洛谷 P4929 【模板】舞蹈链（DLX）

分析

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
题目背景
本题是舞蹈链模板——精确覆盖问题

题目描述
给定一个N行M列的矩阵，矩阵中每个元素要么是1，要么是0

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列j，在你挑选的这些行中，有且仅有一行的第j个元素为1

输入格式
第一行两个数N,M
接下来N行，每行M个数字0或1，表示这个矩阵

输出格式
一行输出若干个数表示答案，两个数之间用空格隔开，输出任一可行方案均可，顺序随意

若无解，输出“No Solution!”（不包含引号）

输入输出样例
输入 #1复制
3 3
0 0 1
1 0 0
0 1 0
输出 #1复制
2 1 3
输入 #2复制
3 3
1 0 1
1 1 0
0 1 1
输出 #2复制
No Solution!
说明/提示
N,M≤500
保证矩阵中1的数量不超过5000个

限制
1s

这是典型的舞蹈链板题. 下面的板子完全遵守【1】中的思想

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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

const int maxn = 505, maxm = 6005; // maxn是行列中的较大者, maxm是1的个数最大值+maxn(列标号个数)
int n,m, u[maxm],d[maxm], l[maxm], r[maxm],row[maxm], col[maxm], h[maxn], ans[maxn], t, cnt[maxn]; // u（上）、d（下）、l（左）、r（右）、row（所在行）、col（所在列）是【1】中说过的每个节点(【1】中的1~16)的6个属性. ans用于存储解, t是【1】中十字双向链表中的标明的元素的编号(即【1】中那16个元素加上列标C1~C7共计23个元素1~23)，h[i]是第i行双向循环链表的虚拟的头结点（注意, h[i]仅仅在建表的时候有用,因为便于头插）,【1】中的1~16这些元素的行列皆>=1, cnt[i]表示第i列含有1的个数

void init() // 初始化舞蹈链
{
	for (int i = 0; i<=m; i++) // 0号标号的元素就是【1】中的head. 1~m就是【1】中的C1~C7
	{
		l[i+1]=i, r[i] = i+1, d[i]=u[i]=i, cnt[i] = 0; // 初始化列标C1~C7的指针
	}
	l[0] = m, r[m] = 0; // head的左侧就是C7, 而C7的右侧就是0（双向循环链表嘛~）
	t = m+1; // 正经的元素（即矩阵中的1）的标号从m+1开始
}

void link(int i, int j) // 第i行、第j列的格子插入舞蹈链. 这里不论是横向还是纵向, 皆采用头插法（水平横向需要采用头插法,所以才需要虚拟出来的h）
{
	cnt[j]++,row[t] = i,col[t] = j; // 注意, 我们现在处理的是t编号的元素
	d[t] = d[j],u[t] = j,u[d[j]] = t,d[j] = t; // 垂直头插, 头结点就是j(即【1】中的Cj)
	if (!h[i]) // 如果头结点还没有, 注意, 我们其实是严格按照了【1】中的图来处理双向十字链表这种数据结构的. 即垂直方向有头结点, 但是水平方向没有
	{
		h[i]=l[t]=r[t]=t;
	}
	else // 水平头插
	{
		l[t]=h[i], r[t]=r[h[i]], l[r[h[i]]]=t, r[h[i]]=t;
	}
	t++;
}

void remove(int c) // 移除c列, 即【1】中所说的标识某一列
{
	r[l[c]] = r[c], l[r[c]]=l[c]; // 处理列标（即C1~C7）这是舞蹈链算法能快速回溯的关键!即并没有去掉⑤和⑥,而只是将①替换成了②,③替换成了④（见图1），为什么要保留⑤和⑥? 因为回溯的时候（即【1】中所谓的回标C_{col}操作）要通过⑤、⑥找到C_{col}原先的前驱和后继
	for (int i = d[c]; i!=c; i = d[i]) // 将col列这一列上所有的元素所在的行上的所有元素都从舞蹈链上移除(即从它们所在的列中移除)
	{
		for (int j = r[i]; j!=i; j = r[j])
		{
			u[d[j]] = u[j], d[u[j]]=d[j], cnt[col[j]]--; // j所在列的1的个数-1
		}
	}
}

void resume(int c) // 【1】中所说的回标col列
{
	l[r[c]] = r[l[c]] = c; // 将col重新接入舞蹈链中, 这里体现链表对于回溯操作的高效! 即图1中②重新换成①,④重新换成③
	for (int i = u[c]; i!=c; i = u[i])
	{
		for (int j = l[i]; j!=i; j = l[j])
		{
			d[u[j]] = u[d[j]] = j, cnt[col[j]]++; // u[j]和d[j]没删掉呢~ 所以能找到原先的前驱和后继
		}
	}
} // 注意, 不难知道resume（恢复）和remove（删除）采用完全相反的顺序（参见【1】搜索"相反"）. 

bool dance(int step) // 起舞吧~ step表示当前决定ans[step]
{
	if (!r[0]) // 说明舞蹈链已经空了——只剩下head节点（即0节点）
	{
		for (int i =0 ; i<step; i++)
		{
			if (i)
			{
				putchar(' ');
			}
			printf("%d", ans[i]);
		}
		return true; // 如果本函数不是返回bool值的, 而是void（即这里仅仅是return）,则可以求出全部解
	}
	int _max = maxn, nxtCol;
	for (int i = r[0]; i; i = r[i]) // 必须要优先开拓1比较少的列, 这样速度比较快, 不然的话, 会被T掉的,找到1最少的列是cnt存在的唯一目的
	{
		if (_max>cnt[i])
		{
			nxtCol = i;
			_max = cnt[i];
		}
	}
	remove(nxtCol); // 移除r[0]这一列(反正这一列肯定是要被覆盖掉的)
	for (int i = d[nxtCol]; i!=nxtCol; i = d[i]) // 开始选择到底是r[0]这一列的哪一行来覆盖r[0](即提供r[0]所需要的这个1)
	{
		ans[step] = row[i]; // step步选择第i这个编号的元素所在的行, 切记, i是元素的编号, 即【1】中的1~16
		for (int j = r[i]; j!=i; j = r[j]) // 逐一标识row[i]所在的行的所有元素所在的列(因为选了row[i]行的话, 则这些列上的1都能被row[i]行提供, 所以这些列都不能再选了)
		{
			remove(col[j]); // 【1】中所说的标识 col[j]列, 即编号为j的元素所在列
		}
		if (dance(step+1)) // 通过上面的标识列, 将舞蹈链的规模大幅减少, 所以递归
		{
			return true;
		}
		for (int j = l[i]; j!=i; j = l[j])
		{
			resume(col[j]); // 按照remove的逆序改回来
		}
	}
	resume(nxtCol); // 将最初标识的r[0]进行回标操作
	return false; // 因为r[0]这一列不论选择哪一行提供r[0]列需要的这个1都不行.
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d%d", &n,&m);
	init();
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1,x; j<=m; j++)
		{
			scanf("%d", &x);
			if (x) // 读入了1了
			{
				link(i,j); // 将该1（i行j列）插入舞蹈链
			}
		}
	} // 构造完毕舞蹈链
	if (!dance(0))
	{
		puts("No Solution!");
	}
	return 0;
}

ac情况

1
2
3
4
5
6
7
8
所属题目
P4929 【模板】舞蹈链（DLX）
评测状态
Accepted
评测分数
100
提交时间
2019-09-15 21:08:29

​ 图1

参考

【1】https://yfsyfs.github.io/2019/09/14/%E8%88%9E%E8%B9%88%E9%93%BE%EF%BC%88dancing-links%EF%BC%89%E7%AE%97%E6%B3%95/