舞蹈链

# **舞蹈链（DLX）** Tags：搜索 ## [作业部落](https://www.zybuluo.com/xzyxzy/note/1205771) ## [评论地址](https://www.cnblogs.com/xzyxzy/p/9278009.html) --- 洛谷的博客版面超好看 ## **一、概述** **特别特别感谢这位童鞋[His blog](https://www.luogu.org/blog/ONE-PIECE/qian-tan-dlx)** 舞蹈链是一种优美的搜索，就像下面这样跳舞～  **舞蹈链用于解决精确覆盖或者重复覆盖的问题** 你可以想象成贪吃蛇的一个上下左右联通的地图 $Dancing Links$就是通过**链表**这样实现的 [网上有图的博客](https://blog.csdn.net/whereisherofrom/article/details/79220897) ## **二、实现** ### **精确覆盖** 精确覆盖大概指的就是数独和八皇后那样的问题，每行每列只允许一个元素 那么就是说每个格子上的点都有若干限制条件（行、列、对角线），每个条件都只允许一个元素 在舞蹈链中（可以把它看作一个表格），每个元素看作一行，限制条件转化为列，选一行删去也同时要删去这一行中所有点所在的列 然后舞蹈链兹瓷快速删除这些东西和快速回溯（复杂度未知） 大概有$init$、$link$、$remove$、$resume$、$dance$五个函数 实现的话看代码吧，有详细的注释 [[luogu1219]八皇后](https://www.luogu.org/problemnew/show/P1219) ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=100100; int ans,nn,o; struct out{int a[14];}Ans[N]; namespace DLX { int n,m,cnt;//长宽，点的数量 int l[N],r[N],u[N],d[N];//上下左右的情况 int row[N],col[N];//每个点所处的行列 int h[N],s[N];//头节点和每列节点数 int ansk[20];//答案 void init(int nn,int mm) { //这个表格被循环套了起来，就像贪吃蛇的地图，左右和上下相通 //预先给第0行的每一列弄一个点 n=nn,m=mm; 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]=cnt=m; memset(h,-1,sizeof(h)); } void link(int R,int C)//在R行C列插入点 { s[C]++;cnt++;//先记录这个点的各种信息 row[cnt]=R; col[cnt]=C; //把列的链表改动 u[cnt]=C; d[cnt]=d[C]; u[d[C]]=cnt; d[C]=cnt; //把行的链表改动 if(h[R]<0) 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; } } void remove(int C)//删除C列以及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]]--;//是减得只剩下1吗（dei） } } void resume(int C)//恢复C列以及C列上有点的行 { r[l[C]]=C; l[r[C]]=C; for(int i=d[C];i!=C;i=d[i]) for(int j=r[i];j!=i;j=r[j]) { u[d[j]]=j; d[u[j]]=j; s[col[j]]++; } } void dance(int deep) { int C=r[0];//找第一个限制条件 if(C>2*nn)//如果所有的行已经被删完就统计答案（能不能>2n） { ans++; for(int i=0,x,y;i<deep;i++) { //记录下来选的点的编号，用编号还原行列 x=ansk[i]%nn; y=(ansk[i]-1)/nn+1; if(x==0) x=nn; Ans[ans].a[y]=x;//x和y是等价的，可以交换 } return; } for(int i=C;i<=nn;i=r[i])//找到点最少的列 /* 这是一处剪枝，因为删掉点最少的列，就是为了满足这个限制条件 需要枚举删掉的点就少一些，从而使得之后的剪枝更高效 相当于把搜索树繁茂的地方留给叶子，而深度越深越容易被剪枝 不加会T */ if(s[i]<s[C]) C=i; remove(C);//删掉这一列 for(int i=d[C];i!=C;i=d[i])//枚举答案是这一列的哪个点，因为每一列只能选一个点，所以枚举选哪个 { ansk[deep]=row[i];//记录答案，这个点编号是row[i] for(int j=r[i];j!=i;j=r[j]) remove(col[j]);//这个点的行也得删了，把这行有点的列也删掉 dance(deep+1); for(int j=r[i];j!=i;j=r[j]) resume(col[j]);//回溯 } resume(C);//回溯过程 } } int cmp(const out&A,const out&B) { int p=0;while(A.a[p]==B.a[p]) p++; return A.a[p]<B.a[p]; } int main() { /// freopen("a.out","w",stdout); scanf("%d",&nn); /* nn*nn个格子，每个格子看作舞蹈链的一行 总共有nn行nn列nn×2-1左对角nn×2-1右对角 共6×nn-2个限制 把每个限制看作一列，进行精准覆盖 */ DLX::init(nn*nn,6*nn-2); for(int i=1;i<=nn;i++) for(int j=1;j<=nn;j++) { o++; DLX::link(o,i);//占据第i行 DLX::link(o,j+nn);//占据第j列（能不能不写这一句） DLX::link(o,i-j+3*nn);//占据第i-j+nn个左上到右下的对角线 DLX::link(o,i+j+4*nn-2);//占据第i+j-1个右上到左下的对角线 } DLX::dance(0);//跳舞啦 sort(Ans+1,Ans+ans+1,cmp); for(int i=1;i<=3;i++,puts("")) for(int j=1;j<=nn;j++) printf("%d ",Ans[i].a[j]); printf("%d\n",ans);return 0; } ``` 重复覆盖的话先留坑