Dancing Links解决Exact Cover问题.
用到了循环双向十字链表.
dfs.
论文一知半解地看了一遍,搜出一篇AC的源码,用注释的方法帮助理解.
HIT ACM
感谢源码po主.链接如下:
http://blog.csdn.net/yysdsyl/article/details/4266876
#include <iostream>
#include <cstdio>
using namespace std;
const int INT_MAX = 2147483647;
struct point {
int L;
int R;
int U;
int D;//四个方向的链表
int Sum;
int x, y;
}p[ 1010 * 1010 ];//这是直接开了一个point类型的数组,没有复用.1000*1000一维
//此处的链表并不是动态分配内存,而是一个静态的数组,只是他们提供的信息可以使得
//这个数组中的元素按照链表的功能运行
int n, m;
int i, j, k;
int map[1001][1001];
int sor[1001];
int flag;
int stack[1001], top;
int Num(int x, int y) {//将二维转化为一维
return x * 1001 + y;
}
//删除c列
//所谓"删除",就是改变链表勾连搜索的关系!
void CoverCol(int c) {
int i, j;
p[ p[ c ].R ].L = p[ c ].L;
p[ p[ c ].L ].R = p[ c ].R;
//首先删除c列第0行
//删除c列中每个有1的行
i = c;
for(i = p[i].D; i != c; i = p[i].D) {//结束条件:因为纵向也是循环的.这里体现了循环链表的方便之处
j = i;//i是向下移动的
p[ p[i].y ].Sum --;//其实就是p[c].Sum--;(把y看成R了..于是理解不能 = =b)
for(j = p[j].R; j != i; j = p[j].R) {//由于是循环链表,一直往右走就能走到左边
p[ p[j].D ].U = p[ j ].U;
p[ p[j].U ].D = p[ j ].D;
}
}
}
//恢复c列
void Release(int c) {//恢复一列只需提供列数
int i, j;
p[ p[ c ].R ].L = c;//列数本身可寻址第0行
p[ p[ c ].L ].R = c;
//恢复c列中每个有1的行
i = c;
for(i = p[i].U; i != c; i = p[i].U) {//居然是循环上移...效果倒是没差
j = i;
p[ p[i].y ].Sum ++;
for(j = p[j].L; j != i; j = p[j].L) {
p[ p[j].D ].U = j;
p[ p[j].U ].D = j;
}
}
}
//正常dfs都是递归
bool dfs(int k) {
int i, j;
if(flag) return 1;//dfs的返回值就是一个bool
//得解输出,stack一路释放完~~~
if(p[ 0 ].R == 0) {
printf("%d", top);
for(i = 0; i < top; i++)
printf(" %d", stack[i]);
puts("");//自带endl..
flag = 1;
return 1;
}
int c = 0; //每次取出没有被覆盖的并且1的个数最小的一列,用于保存结果
int Min = INT_MAX;//一种安全的初始化Min的方式
//i = c;
for(i = p[0].R; i ; i = p[i].R) {//i是列指针,遍历.***0.0的用处就是来初始化这里!所以它的左指针没用
if(p[ p[i].y ].Sum < Min) {//第0行主要用来遍历列
Min = p[ p[i].y ].Sum;
c = i;
}
}
//将这一列删除,同时删除这一列所有上有1的行
CoverCol(c);
i = c;
//枚举c列中有1的的每一行,i向下移动
for(i = p[i].D; i != c; i = p[i].D) {//仍然可看到循环
//p[i].x 作为当前枚举的行，进栈
stack[ top++ ] = p[i].x;//top指向栈顶元素之上位置,因为top表示数量,本就比下标多一
j = i;
/*****对于该枚举的行，删除该行上1的格子所在的列*****/
//其实这种枚举就是一种标定,表示选择的路径(用了递归自身的特点,枚举即标定).
//它实际上也存在
/**"删除"只是脱离主体**///主体就是头指针指的那个
//行本身还是连着的
for(j = p[j].R; j != i; j = p[j].R) {
CoverCol(p[j].y);
}
if ( dfs(k+1) )
return 1;
/**但是为什么要在这时递归??**/
/**因为正常情况下,此时有可能到达终点,即是
从本层调用开始,一个不空的矩阵,在一般情况下(不是仅限于n行1列的话),是会达到全空的.
因此删到这里的时候进行下一次递归**/
//这样看来,就是以枚举的点为交点(列其实是随机选择的,而行是枚举的,也就是说其实就是搜索
//[终于看出来DLX是一种搜索了= =b]
//只是状态的转移是根据十字链表而确定,我们所熟悉的是四方or六方move),将能够删除的全部删除,判断是否
//已经到达终点,若是,成功;否则选择下一个(最小列+枚举行,其实就是从剩余状态中找出一种方案对其深搜的
//策略之一)
//还有,递归的特性:本层函数是k,那么里面包含k+1的调用,
//查看k层函数运行到"调用k+1"之后又做了什么,可以看到和函数开头的呼应
//可以分两种情况分析清楚一个递归函数:
//1.假设函数中的递归调用返回递归截止数据(参考基线情况),说明达到了怎样的终点
//2.假设函数中的递归调用返回失败数据(有时有,有的递归没有),退回的路径是什么
//如果这样下去删不干净(下面的每一层都是return 0了)
//对于该枚举的行，恢复该行上1的格子所在的列
/**恢复,即是回溯**///设想一下,就像一个花卷~@
j = i;
for(j = p[j].L; j != i; j = p[j].L) {//循环左走
Release(p[j].y);
}
top --;//枚举失败,pop掉.这种枚举每次都是不同的,不需要判重
}
//恢复c
Release(c);
return 0;
}
int main() {
int T = 0;//每次循环特殊标记,不用每次清空
while(scanf("%d %d", &n, &m) != EOF) {
T ++;
for(i = 1; i <= n; i++) {//一行一行进行处理
scanf("%d", &k);//1的数目
for(j = 0; j < k; j++) {
scanf("%d", &sor[j]);//存原始数据的一个数组
map[i][sor[j]] = T;//在map上还原图.用T标记!!
}
int lef = Num(i, sor[0]);//转化为一维后最左和最右1的下标
int rig = Num(i, sor[k-1]);
//对数组的赋值过程其实就是链表的建立过程
p[ lef ].L = rig;//循环起来,指针实际上是下标
p[ lef ].x = i;
p[ lef ].y = sor[0];//在图中的坐标
for(j = 1; j < k; j++) {
int cur = Num(i, sor[j]);//循环取出头节点之后的1's
p[ Num(i, sor[j-1]) ].R = cur;//前一个节点的右指针接上
p[ cur ].L = Num(i, sor[j-1]);//新节点的左指针接上
p[ cur ].x = i;
p[ cur ].y = sor[j];
}
p[ rig ].R = lef;//尾节点的右指针循环起来
}
//至此,整张图的每一行的循环双向链表建立完成~,Sum未赋值,默认为0
p[0].R = 1;//图是从第1行开始的,这个第0行的右指针指向了1(也是第0行)???
//第0行有什么妙用??[后文有]
//0的左指针没有循环起来啊[后文有,注释在函数中]
for(i = 1; i <= m; i++) {
int No = Num(0, i);//其实就是i本身...
if(i + 1 <= m)//caution!第一列也没有用!
p[ No ].R = Num(0, i+1);
else
p[ No ].R = 0;//右指针循环起来
//对第0行建立链表,0.0是循环点,不越界就全部连起来
p[ No ].L = Num(0, i-1);
p[ No ].x = 0;
p[ No ].y = i;
p[ No ].Sum = 0;//sum是干啥用的?[后文有]
int last = No;//No就是当前的列指针
for(j = 1; j <= n; j++) {//列一定时,搜索每一行
if( map[j][i] == T ) {//如果此位有1
p[ last ].Sum ++;//第0行节点的sum成员存该行的1数目
int now = Num(j, i);//二维转一维
//开始构建十字链表~~
p[ No ].D = now;//纵向之前节点,挑有1的相连
p[ now ].U = No;//双向十字链表
No = now;//将last更新,that's why it is called 'last'!!!
}
}
p[ No ].D = Num(0, i);
p[ Num(0, i) ].U = No;//纵向循环起来
if( !p[ last ].Sum ) {//若有一列全为0,不可能精确覆盖,直接退出
printf("NO/n");
break;
}
}
if(i == m + 1) {//如果是正常退出(自然限制,不用标记变量,好!)
flag = 0;
top = 0;
dfs(0);//DLX是深搜啊...
if(!flag)
puts("NO");
}
//不是正常退出说明已作出判断
}
return 0;
}
/**总结:DLX使用了基于静态数组的循环双向十字链表的"易恢复性",及其储存稀疏矩阵的简便性,
能较好地解决精确覆盖问题.**/