Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包含一个1。例如下面的矩阵,我们将改矩阵命名为矩阵1
如何利用给定的矩阵求出相应行的集合呢,采用回溯法。假定选择第一行,如下所示
如上图所示,红色那一行是选中的行,这一行有3个1,分别是第3,5,6列。由于这三列已经包含了1,所以把这三列往下标,图中懒得部分包含了3个1,这3个1分别在两行中,把这两行用紫色标出来,根据要求,同一列的1只能有一个,故紫色的两行和红色一行相冲突。那么在接下来的求解中,红色部分、蓝色的部分、紫色的部分都不能用了,把这些部分都删除,得到一个新的矩阵
行分别对应矩阵1中的第2,4,5行,列分别对应1,2,4,7列,于是问题就转化为一个规模更小的精确覆盖问题。我们将该矩阵命名为矩阵2,在矩阵2中选择第一行,如下图所示
按照之前的步骤,进行标示,然后将红色,蓝色,紫色交叉的部分全部删除,这时发现矩阵空了,而红色的一行有0(有0说明这一列没有1覆盖),说明,第1行选择是错误的。 那么回到之前,选择第2行,如下图所示
行对应矩阵2中的第3行,矩阵1中的第5行,列对应矩阵2中的第2,4列,矩阵1中的2,7列。由于剩下的矩阵只有1行,且都是1,所以直接选择这一行,问题就解决,于是该问题的解就是矩阵1中的第一行、矩阵2中的第2行、矩阵3中的第1行。也就是矩阵1中的第1、4、5行。 在求解这个问题的过程中,我们第1步选择第1行是正确的,但是不是每个题目第1步选择都是正确的,如果选择第1行无法求解出结果出来,那么就要推倒之前的选择,从选择第2行开始,以此类推。从上面的求解过程来看,实际算法流程如下:
从如上的求解流程来看,在求解的过程中有大量的缓存矩阵和回溯矩阵的过程。而如何缓存矩阵以及相关的数据(保证后面的回溯能正确恢复数据),也是一个比较头疼的问题(并不是无法解决)。以及在输出结果的时候,如何输出正确的结果(把每一步的选择转换为初始矩阵相应的行)。
Dancing Links的核心是基于双向链表的方便操作(移除、恢复加入),我们用例子来说明:假设双向链表的三个连续的元素,A1、A2、A3,每个元素有两个指针Left和Right,分别指向左边和右边的元素。由定义可知A1.Right=A2,A2.Right=A3,A2.Left=A1,A3.Left=A2。现在把A2这个元素从双向链表中移除(不是删除)出去,那么执行下面的操作就可以了A1.Right=A3,A3.Left=A1,如果要将A2恢复,也只需要修改A1的Right指针和A3的Left指针,也就是A1.Right=A2,A3.Left=A2,但是在很多实际应用中,把双向链表的首尾相连,构成循环双向链表。 Dancing Links中的每个元素不仅是横向循环双向链表中的一份子,又是纵向循环双向链表的一份子,因为准确覆盖问题的矩阵往往是稀疏矩阵(矩阵中,0的个数多于1的个数),Dancing Links仅记录矩阵中值是1的元素。 Dacing Link中的每个元素有6个分量,分别是Left(指向左边的元素)、Right(指向右边的元素)、Up(指向上边的元素)、Down(指向下边的元素)、Col(指向列标的元素)、Row(指向行标的元素) Dancing Links还要准备一些辅助元素
下图就是根据题目构建好的交叉十字循环双向链表
接下来,利用图来解释Dancing Links是如何求解精确覆盖问题。
如上图可知,行2和行4中的一个必是答案的一部分(其他行中没有元素能覆盖列C1),先假设选择的是行2.
把上图中的紫色部分和橙色部分移除,剩下的绿色部分如下图所示:
把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:
把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:
把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:
把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:
把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:
从以上的14步来看,可以把Dancing Links的求解过程表述如下:
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxnode 1001010
#define maxn 1010
using namespace std;
struct DLX {
int n,m;
int U[maxnode],D[maxnode],L[maxnode],R[maxnode],col[maxnode],row[maxnode];
int H[maxn];
int ansed,ans[maxn],size;
void init(int n,int m) {
this->n = n;
this->m = m;
for(int i = 0;i <= m;i++) {
U[i] = i;
D[i] = i;
L[i] = i - 1;
R[i] = i + 1;
col[i] = i;
row[i] = 0;
}
L[0] = m;
R[m] = 0;
size = m;
memset(H,-1,sizeof(H));
memset(ans,0,sizeof(ans));
ansed = 0;
return;
}
void push(int r,int c) {
size++;
D[size] = D[c];
U[size] = c;
U[D[c]] = size;
D[c] = size;
row[size] = r;
col[size] = c;
if(H[r]<0) {
H[r] = size;
R[size] = L[size] = size;
} else {
L[size] = H[r];
R[size] = R[H[r]];
L[R[H[r]]] = size;
R[H[r]] = size;
}
}
void del(int c) {
R[L[c]] = R[c];
L[R[c]] = L[c];
for(int i = D[c];i != c;i = D[i])
for(int j = R[i];j != i;j = R[j]) {
D[U[j]] = D[j];
U[D[j]] = U[j];
}
return;
}
void reback(int c) {
for(int i = U[c];i != c;i = U[i])
for(int j = L[i];j != i;j = L[j]) {
D[U[j]] = j;
U[D[j]] = j;
}
R[L[c]] = c;
L[R[c]] = c;
return ;
}
bool dancing(int dep) {
if(R[0] == 0) {
ansed = dep;
return true;
}
int c = R[0];
del(c);
for(int i = D[c];i != c;i = D[i]) {
ans[dep] = row[i];
for(int j = R[i];j != i;j = R[j])
del(col[j]);
if(dancing(dep + 1))
return true;
for(int j = L[i];j != i;j = L[j])
reback(col[j]);
}
return false;
}
}dlx;
int main() {
int n,m,p,k;
while(scanf("%d%d",&n,&m) == 2) {
dlx.init(n,m);
for(int i = 1;i <= n;i++) {
scanf("%d",&p);
for(int j = 1;j <= p;j++) {
scanf("%d",&k);
dlx.push(i,k);
}
}
if(!dlx.dancing(0))
printf("NO\n");
else {
printf("%d",dlx.ansed);
for(int i = 0;i < dlx.ansed;i++)
printf(" %d",dlx.ans[i]);
printf("\n");
}
}
return 0;
}