Dancing Links初学记

记得原来备战OI的时候，WCX大神就研究过Dancing Links算法并写了一篇blog。后来我还写了个搜索策略的小文章( http://www.cnblogs.com/pdev/p/3952279.html )。当时理解的Dancing Links就是在搜索的时候在尽可能靠近搜索树根的地方剪枝。

其实Dancing Links的具体原意是解决精确覆盖问题：

一个N*M的矩阵，全部由0或1构成。要求在矩阵中拿出几行组成一个新矩阵，使得新矩阵中每一列都恰好有且只有一个1。求具体方案。

Reference：

http://www.cnblogs.com/grenet/p/3145800.html

eg1 : HUSTOJ 1017 http://vjudge.net/problem/viewProblem.action?id=10702

裸的精确覆盖问题

贴一段网上找的代码….直接当模板用233333

Reference：http://www.cnblogs.com/183zyz/archive/2011/08/07/2129886.html

  1 /*Problem: HUST 1017   User: zyzamp  
  2 Memory: 1924 KB   Time: 268 MS  
  3 Language: C++   Result: Accepted */
  4 # include<stdio.h>
  5 # include<string.h>
  6 # include<time.h>
  7 # define N 1005
  8 # define V 102005
  9 int U[V],D[V];
 10 int L[V],R[V];
 11 int C[V];
 12 int H[N],S[N],mark[V];
 13 int size,n,m,OK[N],flag;
 14 void Link(int r,int c)
 15 {
 16     S[c]++;C[size]=c;
 17     U[size]=U[c];D[U[c]]=size;
 18     D[size]=c;U[c]=size;
 19     if(H[r]==-1) H[r]=L[size]=R[size]=size;
 20     else
 21     {
 22         L[size]=L[H[r]];R[L[H[r]]]=size;
 23         R[size]=H[r];L[H[r]]=size;
 24     }
 25     mark[size]=r;
 26     size++;
 27 }
 28 void remove(int c)//删除列
 29 {
 30     int i,j;
 31     L[R[c]]=L[c];
 32     R[L[c]]=R[c];
 33     for(i=D[c];i!=c;i=D[i])
 34     {
 35         for(j=R[i];j!=i;j=R[j])
 36         {
 37             U[D[j]]=U[j],D[U[j]]=D[j];
 38             S[C[j]]--;
 39         }
 40     }
 41 }
 42 void resume(int c)
 43 {
 44     int i,j;
 45     for(i=U[c];i!=c;i=U[i])
 46     {
 47         for(j=L[i];j!=i;j=L[j])
 48         {
 49             U[D[j]]=j;D[U[j]]=j;
 50             S[C[j]]++;
 51         }
 52     }
 53     L[R[c]]=c;
 54     R[L[c]]=c;
 55 }
 56 void Dance(int k)
 57 {
 58     int i,j,Min,c;
 59     if(!R[0]) 
 60     {
 61         flag=1;
 62         printf("%d",k);
 63         for(i=0;i<k;i++)
 64             printf(" %d",mark[OK[i]]);
 65         printf("
");
 66         return;
 67     }
 68     for(Min=N,i=R[0];i;i=R[i])
 69         if(S[i]<Min) Min=S[i],c=i;
 70     remove(c);//删除该列
 71     for(i=D[c];i!=c;i=D[i])
 72     {
 73         OK[k]=i;
 74         //remove(i);
 75         for(j=R[i];j!=i;j=R[j])
 76             remove(C[j]);
 77         Dance(k+1);
 78         if(flag) return;
 79         for(j=L[i];j!=i;j=L[j])
 80             resume(C[j]);
 81         //resume(i);
 82     }
 83     resume(c);
 84 }
 85 int main()
 86 {
 87     int i,j,num;
 88     while(scanf("%d%d",&n,&m)!=EOF)
 89     {
 90         for(i=0;i<=m;i++)
 91         {
 92             S[i]=0;
 93             D[i]=U[i]=i;
 94             L[i+1]=i;R[i]=i+1;
 95         }R[m]=0;
 96         size=m+1;
 97         memset(H,-1,sizeof(H));
 98         memset(mark,0,sizeof(mark));
 99         for(i=1;i<=n;i++)
100         {
101             scanf("%d",&num);
102             while(num--)
103             {
104                 scanf("%d",&j);
105                 Link(i,j);
106             }
107         }
108         flag=0;
109         Dance(0);
110         if(!flag) printf("NO
");
111     }
112     return 0;
113 }

View Code

基本结构：双向十字链表

如图对矩阵中每个元素标号：（见红色字）

像普通的双向链表中的p[i].left、p[i].right一样给每个元素设置指向四个方向的指针

例如上图中对于13有U[13]=12,D[13]=9,L[13]=15,R[13]=14

H[1….n]：每一行第一个1的标号

S[1….m]：每一列中1的个数

运行过程如下:

未完待续~