Dancing links是一种能高效实现Knuth的X算法的技术，它可以使很多搜索问题得到极大的优化。
假设x是一个双向链表中的一个节点，L[x]表示X的前驱，R[x]表示x的后继，
则R[L[x]] = R[x], L[R[x]] = L[x]这一操作可以把x从链表中移除，这是众所周知的，
当然，一个细致的程序员还会用 L[x] = R[x] = x或 L[x] = R[x] = NULL这样的操作来清除x，
以免发生内存泄露，所以只有很少的程序员意识到，若不清除x则 R[L[x]] = x, L[R[x]] = x
这个操作可以把刚才移除的x恢复到之前的链表中，而这样的恢复功能在有些时候是很有用的，
例如，在一个交互性的程序中，用户很可能想撤销他所做的一个或一系列操作，恢复到先前的状态。
另一个典型的应用是在回溯程序中。
精确覆盖问题：给出一个集合S={a,b,c,d,e,f,g}的一些子集S1={c,e,f}, S2={a,d,g},
S3={b,c,f}, S4={a,d},S5={b,g}, S6={d,e,g}，选取哪些子集可以使得A中的元素全部出现并只出现一次，
即用那些子集可以完全覆盖全集S，并且保证没有元素会被重复覆盖？
({S1={c,e,f},S4={a,d},S5={b,g}}是一组解）
我们可以用一个0-1矩阵来表示这些集合：
矩阵M中每一列对应全集中的一个元素，若M[row=i][col=j]=1则表示集合i包含j元素，
如：第一行S1的c、e、f列为1表示S1包含元素c、e、f。
因此我们可以把之前的问题描述为：给定一个由0和1组成的矩阵M，是否能找到一个行的集合，
使得集合中每一列都恰好包含一个1？
不管怎么说，这都是一个很难的问题，当每行恰包含3个1 时，这是个一个NP-完全问题，自然，
作为首选的算法就是回溯了。
解决精确覆盖问题: Knuth 的X算法，它能够找到由特定的01矩阵定义的精确覆盖问题的所有解。
http://blog.csdn.net/sunny606/article/details/7833551
详细的解说：
http://www.cnblogs.com/steady/archive/2011/03/15/1984791.html
这里有很多例题：
http://www.cppblog.com/notonlysuccess/archive/2009/07/10/89701.html
选了poj的两道题：
http://blog.csdn.net/dicpu/article/details/7407163
http://blog.sina.com.cn/s/blog_62ebd4410100g53u.html
http://scturtle.is-programmer.com/posts/27861.html
看了比较久了，还是不会，等以后有时间再搞吧。
poj3740：精确不覆盖分配
题意：
照着别人代码自己写了一下：
注意数组大小要开大点。
#include<cstdio>
#define maxn 700
#define maxm 6666
#define max 0x7fffffff
int n,m,size;
int L[maxm],R[maxm],U[maxm],D[maxm];
int H[maxn],C[maxm],S[maxn];
void init()
{
for(int i=0;i<=m;i++)
{
S[i]=0;
D[i]=U[i]=i;
R[i]=i+1,L[i+1]=i;
}
R[m]=0;
size=m+1;
}
void link(int r,int c)
{
++S[C[size]=c];//新建一个点
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<0)
H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[size]]=size;
L[size]=H[r];
R[H[r]]=size;
}
size++;
}
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[C[j]];//?
}
void resume(int c)
{
R[L[c]]=L[R[c]]=c;
for(int i=U[c];i!=c;i=U[i])
for(int j=L[i];j!=i;j=L[j])
U[D[j]]=D[U[j]]=j,++S[C[j]];
}
bool dancing(int k)
{
if(R[0]==0)
{
puts("Yes, I found it");
return 1;
}
int tmp,c;
for(int tmp=max,i=R[0];i;i=R[i])
{
if(S[i]<tmp)
tmp=S[c=i];
}
remove(c);
for(int i=D[c];i!=c;i=D[i])
{
for(int j=R[i];j!=i;j=R[j]) remove(C[j]);//?
if(dancing(k+1)) return 1;
for(int j=L[i];j!=i;j=L[j]) resume(C[j]);
}
resume(c);
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=1; i<=n; i++)
{
H[i]=-1;
for(int j=1; j<=m; j++)
{
int a;
scanf("%d",&a);
if(a)
link(i,j);
}
}
if(!dancing(0))
puts("It is impossible");
}
return 0;
}
我想了很久才想清楚：
删除的程序是按行，列，行来进行的。先找S【】最小的列，然后找有哪些行与此列交叉，遍历每个行，把除此列外的交叉点，本行其他的所有交叉点所在行去掉，然后再吧所在列去掉，最后吧此列上的交叉点的行在全部去掉。