题解 P4929 【【模板】舞蹈链（DLX）】
我来水一波题解分享一下我的解法。
算法分析
首先看到这道题可以想到什么？
暴力！
对的没错这题正解就是暴力（滑稽
那我们怎么暴力呢？
依次枚举每行是否取走然后判断是否合法（T到飞起）
我们可以依次枚举每列出现的行，然后给这行上出现的 1 所在列打上标记，删掉含打上标记的行，然后换一列枚举。
没看懂？上图： 图中的数字是输入时给的矩阵，红线画出的是当前枚举的列，绿线画出的是当前枚举的行，黄线画出的是被打上标记的列，蓝线画出的是当前删掉的行。
我们从第一列开始枚举，先枚举第一列上的第一次出现的行第一行。
第一行经过的列有第一、二和五列，我们给它们打上标记。
接下来进行删除。可以看到第二行由于第二列被打上标记而被删除了，第四行也因第一列被打上标记而壮烈牺牲了。
如上步骤重复多次，如果所有列都打上了标记就输出解，如果当前枚举的行无解则回溯。
那问题来了：怎么删行？
这不好说，把那一行用 0 赋一遍就行了。
这样的话每次删行都要遍历一遍。会 T 到飞起啊。
但注意到 1 的数量不超过 5000 个。
那么我们每次只需要把 1 赋成 0 就行了，没必要把 0 赋成 0。
（上面这么说只是方便理解，实际操作中并无赋 0 操作。）
那接下来我们进入重点。
舞蹈链分析
舞蹈连是什么？
二维双向循环十字链表。
翻译成人话就长下面这样：
差点没画死我。
蓝色的是列虚拟节点，黄色的是行虚拟节点，红色的是普通节点。
每个节点都储存着它上下相邻的 1 所在行和左右相邻的 1 所在的列。
（这里只是方便描述，实际操作时按照真实的上下左右储存比较麻烦，故只需使链表可以遍历行和列的元素即可。可对比一维数组链表理解。）
为了快速找到行和列，我们可以在每行左边加入行虚拟节点，每列上面加入列虚拟节点。
特殊的，所有的列虚拟节点也算一行，故要在所有的列虚拟节点前加入一个行虚拟节点。当有列打上标记时便将那个列的列虚拟节点删除。
所以我们发现打了标记的列都被删了那么标记也就没有用了。
（在实际操作中不需要新开数组，一般以每行或列的第 0 个作为虚拟节点。自然，列虚拟节点的那一行行号为 0）
我们发现要满足三个操作：建设银行，删除行（剪枝）和加入行（回溯和建表）。
为什么要建行呢？建舞蹈链呢？工商银行它不香吗。
可以发现每行的节点之间的相邻情况在枚举过程中不会发生变化，所以在读入时就可以把同行节点之间的相邻关系即左右建好，建完后把该行用加入行加入到链表中就行了。
怎么建同行中的左右关系呢？
还记得怎么建一维的双向循环链表的吗？
都研究舞蹈链了没有人没学过吧。
就是对每列的节点建一个双向循环链表了。
只不过行虚拟节点要建在该行最前面。
那行与行之间的上下关系呢？
插入时遍历该行所有节点，把该节点像一维的双向循环链表一样插入该列末尾即可（注意不一定要插到原位置）。
删除时遍历该行所有节点，把该节点像一维的双向循环链表一样删除即可。人性的本质。
还要做两个优化，一个是每次先枚举剩余节点最少的列（优化搜索顺序），另一个是枚举时插入的顺序要和删除的顺序相反（我也不知道为什么要这么干）。
用事实证明优化二有多重要：
-
优化一和优化二都没做的
-
做了优化一没做优化二的
-
优化一和优化二都做了的
代码分析
我知道我变量名是乱取的。那我就用
紫名几乎每行一句的注释将功补过吧。
还是补充说明一下：n,m,a 是原题给出的行数列数和矩阵，o 用来记录每列现存多少 1 以便进行优化一，ans,con 记录答案（类似栈），t 记录是否有解以便找到解及时退出。
//珍爱账号，远离JC
int n,m,a[511][511],o[511],ans[511],con,t;//同上
struct dlx//写在结构体里方便以后直接使用
{
int u[511][511],d[511][511],l[511][511],r[511][511];//上下左右指针
void buiro(int x)//建行
{
for(register int y=1; y<=m; ++y)//枚举该行每个数
{
if(!a[x][y])//如果这个数是1
{
r[x][y]=0;//为了循环将该数右指针指向该行虚拟节点
l[x][y]=l[x][0];//将该数左指针指向该行虚拟节点左指针节点即末尾
r[x][l[x][y]]=y;//是双向链表所以指回来
l[x][r[x][y]]=y;//同上
}
}
}
void addro(int x)//加入行，与建行差不多
{
for(register int y=r[x][0]; y; y=r[x][y])//枚举该行所有节点
{
d[x][y]=0;
u[x][y]=u[0][y];
d[u[x][y]][y]=x;
u[d[x][y]][y]=x;
o[y]++;//所在列 1 的数量加 1
}
}
void delro(int x)//删除行
{
for(register int y=l[x][0]; y; y=l[x][y])//倒序枚举该行所有节点
{
d[u[x][y]][y]=d[x][y];//该节点的上相邻节点的上指针直接跳过该节点指向该节点下指针节点
u[d[x][y]][y]=u[x][y];//同上
o[y]--;//所在列 1 的数量减 1
}
}
} c;//对象（OP术语即结构体变量）
void dfs()//枚举
{
if(!c.r[0][0])//如果列虚拟节点的那一行的行虚拟节点右节点指向自己即列都被删完了
{
for(register int i=0; i<con; ++i)//遍历 ans 数组
printf("%d ",ans[i]);//输出解
t=1;//t 赋 1 以快速退出
return;//退出当前函数
}
register int g=INT_MAX,p=0;//g 是现存节点中最小的 o[i]，p 是拥有最小的 o[i] 的列的编号
for(register int i=c.r[0][0]; i; i=c.r[0][i])//遍历所有现存的列
{
if(g>o[i])//如果小于当前最小 o[i]
g=o[p=i];//把 g 赋成 o[i]，p 赋成 i
}
int v[511],k=0;//倒序插入会打乱该列顺序，需要我们记录所有需要枚举的行
for(register int i=c.d[0][p]; i; i=c.d[i][p])//遍历第 p 列
{
v[k++]=i;//把列上的所有行加入 v 数组
}
for(int i=0;i<k;++i)//枚举所有需要枚举的行
{
int s[511],w=0;//记录被删掉的列以便回溯
for(register int j=c.l[v[i]][0]; j; j=c.l[v[i]][j])//枚举当前行中出现的列
{
c.r[0][c.l[0][j]]=c.r[0][j];//删除此列虚拟节点
c.l[0][c.r[0][j]]=c.l[0][j];
while(c.d[0][j])//枚举出现在此列的行
c.delro(s[w++]=c.d[0][j]);//并删掉它
}
ans[con++]=v[i];//将枚举行的加入 ans 数组
dfs();//继续枚举
if(t)//如果找到答案
return;//就快速退出
con--;//否则将当前枚举的行弹出
for(register int j=c.r[v[i]][0]; j&&f[j]; j=c.r[v[i]][j])//遍历因当前行而删掉的列
{
c.r[0][j]=0;//将它的列虚拟节点恢复
c.l[0][j]=c.l[0][0];
c.r[0][c.l[0][j]]=j;
c.l[0][c.r[0][j]]=j;
}
for(register int j=w-1; j>=0; --j)//倒序遍历因当前行而删掉的行
c.addro(s[j]);//并恢复它
}
}
int main()//主函数
{
register char h;//快读使用
scanf("%d%d",&n,&m);//读入n、m
c.buiro(0);//建列虚拟节点的那一行
for(register int i=1; i<=n; ++i)//当前行
{
for(register int j=1; j<=m; ++j)//当前列
{
do
{
h=getchar();
}
while(h!='0'&&h!='1');//快读
a[i][j]='1'-h;//存进 a 矩阵
}
c.buiro(i);//先建行
c.addro(i);//再加入当前行
}
dfs();//枚举
if(!t)//如果无解
printf("No Solution!");//则输出
}当然，舞蹈链的写法有很多，别的题解大部分是将上下左右指针存在一维数组里，而我将它们存在二维数组里，虽然占空间但更方便好写。
当然，舞蹈链不仅能解决精准覆盖问题，还是解决数独问题、八皇后问题的利器。
麻麻再也不用担心我被靶形数独卡了
完结撒花\(^o^)/