写在前面
请和我起舞趁着故事还没有结束，天亮后让一切恢复。
用处
高效解决精确覆盖问题和完全覆盖问题。（诡异小搜索）
精确覆盖问题
定义
在全集\(S\)中有子集\(T_1,T_2,\dots , T_n\)从中选择若干个子集，使\(S\)中每一个元素在这些自给中分别恰好出现一次。
问题转化
给定一个\(n\)行\(m\)列的\(0,1\)矩阵（每行是一个集合，列代表每一个元素），选择其中几行，使每列恰好只有一个\(1\)。
DLX求解
直接大暴搜的时间复杂度是\(O(m2^n)\)，妥妥的寄掉了\(\dots\)
所以\(\dots\)接着奏乐，接着舞！
具体过程：
递归删表，如果把表删完，代表每一列都被\(1\)精确覆盖，找到一组答案，如果没有删完，就要向下递归
- 找\(1\)的个数最少的列（\(1\)的个数越少，分支越少）。
- 把这一列的列表头删除（假的删除，假设这一列的列表头为\(x\)，左边连接\(a\)，右边连接\(b\)，把\(a\)指向\(x\)的指针指向\(b\)，\(b\)指向\(x\)的指针指向\(a\)，但可以通过\(x\)的指针找到\(x\)左右的\(a和\)\(b\))。
- 把这一列的相关的行（这一列在哪一行有\(1\)就与哪一行相关）删除（这一列中各个指针不变，方便还原）。
- 记录下暂时选定哪一行。
- 把这一行相关的列（这一行在哪一列有\(1\)就与哪一行有\(1\)就与哪一行相关）删除，并一同删除被删除列相关的行。
- 继续向下递归。
- 如果这次选择不合法，恢复所删除的列和这一列相关的行。
为了完成灵活的删除和恢复操作，需要使用双向循环十字链表。在双向循环十字链表中每一个元素在横竖交点位置，每一个元素有四个指针，分别指向上下左右相邻的元素，链表左右边界相连，上下边界相连，完成循环。
举个形象的栗子
P4929
这是给定矩阵：
现在画出由以上矩阵构造的循环十字链表：
其中每个点带有\(6\)种属性：十字链表中的\(4\)个指针\(l,r,u,d\)，所在的行\(row\)，所在的列\(col\)。
在上图中有两种数字：
- 从\(7\)到\(21\)为给定矩阵中出现的\(1\)
- 从\(0\)到\(6\)为列表头，记录哪一列存在。
现在我们找到最左面\(1\)的个数最少的列为第\(1\)列，删去第\(1\)列，再删去与第\(1\)列相关的第\(2\)，\(4\)行，与第\(2\)行相关的第\(5\)，\(6\)列，与第\(5\)，\(6\)列相关的第\(5\)，\(6\)行，与第\(4\)行相关的第\(5\)列，和与第\(5\)列相关的行。
这是删除完一轮的样子：
之后再重复删除下一列，之后发现\(\dots\)寄了，第\(4\)列有剩余，所以恢复上次删除（选中）的行列，再选择其它的。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=5510;
int u[maxn],d[maxn],l[maxn],r[maxn],cnt;
int l1[maxn],r1[maxn],h[maxn],s[maxn],ans[maxn];
void insert(int x,int y)
{
l1[++cnt]=y; r1[cnt]=x; s[y]++;
u[cnt]=u[y]; d[u[y]]=cnt; d[cnt]=y; u[y]=cnt;
if(h[x]==0) h[x]=r[cnt]=l[cnt]=cnt;
else
{
l[cnt]=l[h[x]]; r[l[h[x]]]=cnt; r[cnt]=h[x]; l[h[x]]=cnt;
}
}
void del(int y)
{
r[l[y]]=r[y]; l[r[y]]=l[y];
for(int i=d[y];i!=y;i=d[i])
{
for(int j=r[i];j!=i;j=r[j])
{
u[d[j]]=u[j]; d[u[j]]=d[j]; s[l1[j]]--;
}
}
}
void resort(int y)
{
r[l[y]]=y; l[r[y]]=y;
for(int i=u[y];i!=y;i=u[i])
{
for(int j=l[i];j!=i;j=l[j])
{
u[d[j]]=j; d[u[j]]=j; s[l1[j]]++;
}
}
}
int dance(int a)
{
if(r[0]==0)
{
for(int i=0;i<a;i++)
{
printf("%d ",ans[i]);
}
return 1;
}
int y=r[0];
for(int i=r[0];i!=0;i=r[i])
{
if(s[i]<s[y]) y=i;
}
del(y);
for(int i=d[y];i!=y;i=d[i])
{
ans[a]=r1[i];
for(int j=r[i];j!=i;j=r[j])
{
del(l1[j]);
}
if(dance(a+1)) return 1;
for(int j=l[i];j!=i;j=l[j])
{
resort(l1[j]);
}
}
resort(y);
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=m;i++)
{
u[i]=d[i]=i; l[i]=i-1; r[i]=i+1;
}
l[0]=m; r[m]=0; cnt=m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x; scanf("%d",&x);
if(x) insert(i,j);
}
}
if(!dance(0)) cout<<"No Solution!";
}