首页 > 代码库 > Dancing Links 小结 (因为之前丢了一次稿，未完待续)
Dancing Links 小结 (因为之前丢了一次稿，未完待续)
Dancing Links (DLX)是Knuth为了解决精确覆盖问题而提出的算法，很多搜索问题可以转化位精确覆盖问题从而使用Dancing Links解决（效率会比DFS高很多，因为里面常常蕴涵着意想不到的剪枝）
信息学竞赛中的DLX的问题类似网络流，只需建图+贴版即可
参考文献：
1、DLX的原理：Knuth的论文：
原版：http://arxiv.org/abs/cs/0011047
翻译版：http://wenku.baidu.com/view/d8f13dc45fbfc77da269b126.html
2、DLX在搜索中的应用（DLX应用于信息学竞赛的论文）：http://bbs.whu.edu.cn/wForum/elite.php?file=%2Fgroups%2FGROUP_3%2FACM_ICPC%2Fnx08%2FD.08010000%2FM.1215524645.R0&ap=563
首先介绍精确覆盖问题概念：
精确覆盖：在一个全集$X$中若干子集的集合为$S$，精确覆盖是指，$S$的子集$S*$，满足$X$中的每一个元素在$S*$中\textbf{恰好}出现一次。
即：给你一个0-1矩阵，选取若干行，使得选取的行组成的新矩阵的每一列有且仅有一个1
关于DLX的原理这里就不详细介绍了，有兴趣了解者可以去阅读Knuth的论文
DLX精确覆盖模板(From kuangbin)：
1 const int maxnode = 100010; 2 const int maxr = 1010; 3 const int maxc = 1010; 4 struct DLX 5 { 6 int n, m, size; 7 int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; 8 int H[maxc], S[maxr]; 9 int ansd, ans[maxc];10 void init(int _n, int _m)11 {12 n = _n;13 m = _m;14 for (int i = 0; i <= m; i++)15 {16 S[i] = 0;17 U[i] = D[i] = i;18 L[i] = i - 1;19 R[i] = i + 1;20 }21 R[m] = 0; L[0] = m;22 size = m;23 for (int i = 1; i <= n; i++)24 H[i] = -1;25 }26 void Link(int r, int c)27 {28 ++S[Col[++size] = c];29 Row[size] = r;30 D[size] = D[c];31 U[D[c]] = size;32 U[size] = c;33 D[c] = size;34 if (H[r] < 0)H[r] = L[size] = R[size] = size;35 else36 {37 R[size] = R[H[r]];38 L[R[H[r]]] = size;39 L[size] = H[r];40 R[H[r]] = size;41 }42 }43 void remove(int c)44 {45 L[R[c]] = L[c]; R[L[c]] = R[c];46 for (int i = D[c]; i != c; i = D[i])47 for (int j = R[i]; j != i; j = R[j])48 {49 U[D[j]] = U[j];50 D[U[j]] = D[j];51 --S[Col[j]];52 }53 }54 void resume(int c)55 {56 for (int i = U[c]; i != c; i = U[i])57 for (int j = L[i]; j != i; j = L[j])58 ++S[Col[U[D[j]] = D[U[j]] = j]];59 L[R[c]] = R[L[c]] = c;60 }61 //d为递归深度62 bool Dance(int d)63 {64 if (R[0] == 0)65 {66 ansd = d;67 return true;68 }69 int c = R[0];70 for (int i = R[0]; i != 0; i = R[i])71 if (S[i] < S[c])72 c = i;73 remove(c);74 for (int i = D[c]; i != c; i = D[i])75 {76 ans[d] = Row[i];77 for (int j = R[i]; j != i; j = R[j])remove(Col[j]);78 if (Dance(d + 1))return true;79 for (int j = L[i]; j != i; j = L[j])resume(Col[j]);80 }81 resume(c);82 return false;83 }84 };
PS：init函数初始化，0-1矩阵中为1的位置(i,j)用Link(i,j)添加约束，Dance函数为解决过程(bool表示能否完成)，ansd为选取的数量，and[]为选取的行
精确覆盖问题可以延伸为重复覆盖问题，定义如下：
重复覆盖：在一个全集$X$中若干子集的集合为$S$，重复覆盖是指，$S$的子集$S*$，满足$X$中的每一个元素在$S*$中\textbf{至少}出现一次。
即：给你一个0-1矩阵，选取若干行，使得选取的行组成的新矩阵的每一列至少有一个1
DLX重复覆盖模板
1 const int maxnode = 360000; 2 const int maxc = 500; 3 const int maxr = 500; 4 const int inf = 0x3f3f3f3f; 5 struct DLX 6 { 7 int L[maxnode], R[maxnode], D[maxnode], U[maxnode], C[maxnode]; 8 int S[maxc], H[maxr], size; 9 int ans;10 ///不需要S域11 void Link(int r, int c)12 {13 S[c]++; C[size] = c;14 U[size] = U[c]; D[U[c]] = size;15 D[size] = c; U[c] = size;16 if (H[r] == -1) H[r] = L[size] = R[size] = size;17 else18 {19 L[size] = L[H[r]]; R[L[H[r]]] = size;20 R[size] = H[r]; L[H[r]] = size;21 }22 size++;23 }24 void remove(int c)25 {26 for (int i = D[c]; i != c; i = D[i])27 L[R[i]] = L[i], R[L[i]] = R[i];28 }29 void resume(int c)30 {31 for (int i = U[c]; i != c; i = U[i])32 L[R[i]] = R[L[i]] = i;33 }34 int h() ///用精确覆盖去估算剪枝35 {36 int ret = 0;37 bool vis[maxc];38 memset (vis, false, sizeof(vis));39 for (int i = R[0]; i; i = R[i])40 {41 if (vis[i])continue;42 ret++;43 vis[i] = true;44 for (int j = D[i]; j != i; j = D[j])45 for (int k = R[j]; k != j; k = R[k])46 vis[C[k]] = true;47 }48 return ret;49 }50 //根据具体问题选择限制搜索深度或直接求解。51 bool Dance(int k)52 {53 if (k + h() >= ans) return 0;54 if (!R[0])55 {56 if (k < ans)ans = k;57 return 1;58 }59 int c = R[0];60 for (int i = R[0]; i; i = R[i])61 if (S[i] < S[c])c = i;62 for (int i = D[c]; i != c; i = D[i])63 {64 remove(i);65 for (int j = R[i]; j != i; j = R[j])66 remove(j);67 Dance(k + 1);68 for (int j = L[i]; j != i; j = L[j])69 resume(j);70 resume(i);71 }72 return 0;73 }74 void initL(int x) ///col is 1~x,row start from 175 {76 for (int i = 0; i <= x; ++i)77 {78 S[i] = 0;79 D[i] = U[i] = i;80 L[i + 1] = i; R[i] = i + 1;81 }///对列表头初始化82 R[x] = 0;83 size = x + 1; ///真正的元素从m+1开始84 memset (H, -1, sizeof(H));85 ///mark每个位置的名字86 }87 };
输入：Link()
输出：ans, bool Dance(int k)
重点来了：如何建图？这里选取典型例题说明
(因为之前丢了一次稿，未完待续)
Dancing Links 小结 (因为之前丢了一次稿，未完待续)