Dancing links X 学习笔记
想起以前玩过一个叫数织的游戏，于是就学了。
Dancing links X 分为 Dancing links 和 X 算法。
X 算法
解决类覆盖问题的算法，这里讲精确覆盖。
在一个全集
这么讲有点抽象。简单来说就是假设我有一段数列长度为 {1,2,3,4},{1,3,5,7},{5,7},{5,6,7},{2,3,4,5,6,7}，那么我要在这些子集中选若干个使得 [1,n] 中的每一个元素有且仅有出现一次。那么很显然我应该选择子集 1 与子集 4。
我们把这些子集变成一个矩阵 1。
求解的便是让每一列有且仅有一个 1 的方案。
考虑搜索，即我们开始枚举 {1,2,3,4} 有一个 1 了，那么选择其他行时就不能在 {1,2,3,4} 中任何一个位置有 1。即我们把 {1,2,3,4} 列与在 {1,2,3,4} 列有 1 的行删去，变成一个新矩阵 2。
那么我们继续对新矩阵 2 枚举。先枚举
可以发现已经没有子集可选，但矩阵未覆盖完，覆盖失败。
回到矩阵 2，此时枚举到
从上面的求解过程来看，我们可以把 X 算法的过程总结一下：
-
从矩阵中选择一行。
-
根据定义，标示矩阵中其他行的元素。
-
删除相关行和列的元素，得到新矩阵。
-
如果新矩阵是空矩阵，并且之前的一行都是 1，那么求解结束，跳转到6；新矩阵不是空矩阵，继续求解，跳转到 1；新矩阵是空矩阵，之前的一行中有 0，跳转到 5。
-
说明之前的选择有误，回溯到之前的一个矩阵，跳转到 1；如果没有矩阵可以回溯，说明该问题无解，跳转到 7。
-
求解结束，把结果输出。
-
求解结束，输出无解消息。
从上述求解过程中，我们会发现其中有大量删除矩阵和恢复矩阵的操作，这便是一个新的问题。那么此时我们就需要 Dancing links 算法解决这一操作。
Dancing links
Dancing links 的核心是十字循环双向链的方便操作，使用 Dancing links 我们可以在较短时间内完成删除和恢复矩阵的操作。
链表没什么好说的是个人就会，所以直接看代码。
0. 矩阵变量定义
int n,m;
int cnt; //节点数
int l[M],r[M],u[M],d[M],row[M],col[M]; //左、右、上、下、行、列信息
int h[M],s[M]; //每行的头节点，每列的节点数（便于 Dancing links 操作）
int ans[M]; //最终的答案1. 初始化矩阵
void init(){
for(int i=0;i<=m;++i){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof h);
memset(s,0,sizeof s); //十字循环链表基本初始化
cnt=m+1; //开始有 0 节点和各行头节点
}2. 插入 1 点
void link(int R,int C){
++s[C];
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt; //十字链表原理
if(h[R]==-1) h[R]=l[cnt]=r[cnt]=cnt; //该行没点的话当前点的左右节点都是自己（循环链表）
else {
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
++cnt;
}3. 删除与恢复矩阵
void remove(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]){
u[d[j]]=u[j];
d[u[j]]=d[j];
--s[col[j]];
}
}
} //删除 C 列和 C 列上有点的行
void resume(int C){
for(int i=u[C];i!=C;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
++s[col[j]];
}
}
r[l[C]]=C;
l[r[C]]=C;
} //恢复 C 列和 C 列上有点的行4. 核心部分搜索 dance
bool dance(int dep){
if(!r[0]){ //如果矩阵已经删除完则找到了一组解
for(int i=0;i<dep;++i) cout<<ans[i]<<' ';
return 1;
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i]) if(s[i]<s[c]) c=i; //找到点最少的列，以减少决策树，节省时间
remove(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]) remove(col[j]); //删除矩阵
if(dance(dep+1)) return 1;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]); //回溯矩阵
}
resume(c);
return 0;
}【模板】舞蹈链（DLX）
实际上就是把上面的几块代码拼在一起。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define M 300005
int n,m,cnt;
int l[M],r[M],u[M],d[M],row[M],col[M];
int h[M],s[M],ans[M];
void init(){
for(int i=0;i<=m;++i){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof h);
memset(s,0,sizeof s);
cnt=m+1;
}
void link(int R,int C){
++s[C];
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
if(h[R]==-1) h[R]=l[cnt]=r[cnt]=cnt;
else {
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
++cnt;
}
void remove(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]){
u[d[j]]=u[j];
d[u[j]]=d[j];
--s[col[j]];
}
}
}
void resume(int C){
for(int i=u[C];i!=C;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
++s[col[j]];
}
}
r[l[C]]=C;
l[r[C]]=C;
}
bool dance(int dep){
if(!r[0]){
for(int i=0;i<dep;++i) cout<<ans[i]<<' ';
return 1;
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i]) if(s[i]<s[c]) c=i;
remove(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]) remove(col[j]);
if(dance(dep+1)) return 1;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
}
resume(c);
return 0;
}
int main(){
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
init();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
bool f;
cin>>f;
if(f) link(i,j);
}
}
if(!dance(0)) cout<<"No Solution!";
return 0;
}