(Dance links X)
(Dance) (links) (X)是一种高效的处理精准覆盖问题的算法
常见精准覆盖问题包括但不限于：棋盘问题、数度问题、(k)皇后问题（话说用爆搜这不杀鸡一样？
经典题目：八皇后、靶形数独、智(障)慧珠
(DLX)算法是基于对(X)算法的优化，而(X)算法的本质是爆搜，(DLX)只不过是在(X)算法的基础上套用了一层神奇的数据结构——四向循环链表，以实现高效插入删除行。
其主要思想是：
将全集中的每个元素对应矩阵中的一个列，每个集合对应一个行。
每次任选一个行，随即把该行和该行上有点的列和和包含这些列的行删除。
每步选择之间用爆搜来转移 ， 快速删除行列使用四向循环链表解决
大致就是这样
时空复杂度
首先(Dance) (links) (X)的空间复杂度与该矩阵的(1)的数目有关
时间复杂度为(O()玄学())
但是在(P4929-DLX)模板中，时间复杂度大概为(O(c^n))
(n)是矩阵 (1) 的个数，(c)是某个很接近(1(>1))的常数
在座的各位应该都听过那个(1.01^{365})来描述努力成果的扯淡故事，显然在生活中它是不存在的，但在(Dance) (link) (X)中它确可能达到这个量级
所以我们需要做好万全的准备
(Optimization) (1)
按照正常dfs剪枝的套路，每步选取最小的集合可以大大简化搜索树大小
int co = r[0];
for(int i=r[0];i!=0;i=r[i])
{
if(si[i] < si[co]) co= i;
}
del(co);
(Optimization) (2)
这一步非常玄学，我也没大看明白为什么这样更优
把(back)操作从(delete)的反向来做（大致就是(delete)时用(r)指针右跳，(back)时用(l)指针左跳
inline void back(int co)
{
for(int i=up[co] ; i!=co;i=up[i])
{
for(int j=l[i];j!=i;j = l[j])
{
dn[up[j]] = j;
up[dn[j]] = j;
++si[col[j]];
}
}
r[l[co]] = co;
l[r[co]] = co;
}
for(int j=r[i] ; j!=i;j = r[j]) del(col[j]);
if(dance(dep + 1) == 1) return 1;
for(int j=l[i];j!=i;j = l[j])back(col[j]);
(Dance)——开始起舞
随指尖而舞
——元歌《王者荣耀》
inline bool dance(int dep) // dep表示深度
{
if(r[0]==0) //代表每个元素都已经被处理完美了
{
print();
return 1;
}
int co = r[0];
for(int i=r[0];i!=0;i=r[i]) if(si[i] < si[co]) co= i; // Optimization_1
del(co);//随便删一列
for(int i=dn[co];i!=co;i = dn[i])//从该列中枚举要保留的行
{
int ro = row[i];
Ans[dep] = ro;
for(int j=r[i] ; j!=i;j = r[j]) del(col[j]);//表示这些列暂时已经处理好了
if(dance(dep + 1) == 1) return 1;
for(int j=l[i];j!=i;j = l[j])back(col[j]);//Optimization_2
}
back(co);//回溯
return 0;
}
(details)
(insert)、(delete)、(back)按照链表正常写就行了也没啥（虽然因为这些东西调了很久
(Code)
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define int long long
template<typename _T>
inline void read(_T &x)
{
x= 0 ;int f =1;char s=getchar();
while(s<'0' ||s>'9') {f =1;if(s == '-')f =- 1;s=getchar();}
while('0'<=s&&s<='9'){x = (x<<3) + (x<<1) + s - '0';s= getchar();}
x*=f;
}
struct Dance_links_X{
int n,m,cnt;
int Ans[23333];
int up[23333],r[23333];
int dn[23333],l[23333],head[23333];
int row[233333],col[23333];
int si[23333];
inline void Init()
{
for(int i=0;i<=m;i++)
{
r[i] = i+1;
l[i] = i-1;
up[i] = dn[i] = i;
}
memset(head , -1, sizeof(head));
r[m] = 0;
l[0] = m;
cnt = m;
}
inline void insert(int ro,int co)
{
col[++cnt] = co;
++si[co];
row[cnt] = ro;
up[cnt] = co;
dn[cnt] = dn[co];
up[dn[co]] = cnt;
dn[co] = cnt;
if(-1 != head[ro])
{
l[cnt] = head[ro];
r[cnt] = r[head[ro]];
l[r[head[ro]]] = cnt;
r[head[ro]] = cnt;
}
else head[ro] = l[cnt] = r[cnt] = cnt;
}
inline void del(int co)
{
r[l[co]] = r[co];
l[r[co]] = l[co];
for(int i=dn[co] ; i!=co;i=dn[i])
{
for(int j=r[i];j!=i;j = r[j])
{
dn[up[j]] = dn[j];
up[dn[j]] = up[j];
--si[col[j]];
}
}
}
inline void back(int co)
{
for(int i=up[co] ; i!=co;i=up[i])
{
for(int j=l[i];j!=i;j = l[j])
{
dn[up[j]] = j;
up[dn[j]] = j;
++si[col[j]];
}
}
r[l[co]] = co;
l[r[co]] = co;
}
inline void print()
{
int i= -1;
while(Ans[i+1])
{
printf("%lld ",Ans[++i]);
}
}
inline bool dance(int dep)
{
if(r[0]==0)
{
print();
return 1;
}
int co = r[0];
for(int i=r[0];i!=0;i=r[i]) if(si[i] < si[co]) co= i;
del(co);
for(int i=dn[co];i!=co;i = dn[i])
{
int ro = row[i];
Ans[dep] = ro;
for(int j=r[i] ; j!=i;j = r[j]) del(col[j]);
if(dance(dep + 1) == 1) return 1;
for(int j=l[i];j!=i;j = l[j])back(col[j]);
}
back(co);
return 0;
}
}dlx;
signed main()
{
int x,y;
read(x);
read(y);
dlx.n = x;
dlx.m = y;
dlx.Init();
for(int i=1;i<=x;i++)
{
for(int j=1,vl;j<=y;j++)
{
read(vl);
if(vl) dlx.insert(i,j);
}
}
if(!dlx.dance(0)) printf("No Solution!");
}
(End)
Dance_links_X作为一种冷门算法在考场上遇到的可能性不大，就算遇到了也可以用爆搜剪枝剪过去。
但其中所用到的数据结构——四向循环链表，其思想与特点需要认真理解，很可能在一些莫名其妙的构造题或是思维性数据结构题中遇到，显然是有掌握的必要的。
在处理数独问题中有着巨大优势，其使用核心就是将数独问题转化为精确覆盖问题