Dancing Links 小结 (因为之前丢了一次稿，未完待续)

Dancing Links (DLX)是Knuth为了解决精确覆盖问题而提出的算法，很多搜索问题可以转化位精确覆盖问题从而使用Dancing Links解决（效率会比DFS高很多，因为里面常常蕴涵着意想不到的剪枝）

信息学竞赛中的DLX的问题类似网络流，只需建图+贴版即可

参考文献：

1、DLX的原理：Knuth的论文：

翻译版：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*$中 extbf{恰好}出现一次。

即：给你一个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         else
36         {
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 };

View Code

PS：init函数初始化，0-1矩阵中为1的位置(i,j)用Link(i,j)添加约束，Dance函数为解决过程(bool表示能否完成)，ansd为选取的数量，and[]为选取的行

精确覆盖问题可以延伸为重复覆盖问题，定义如下：

重复覆盖：在一个全集$X$中若干子集的集合为$S$，重复覆盖是指，$S$的子集$S*$，满足$X$中的每一个元素在$S*$中 extbf{至少}出现一次。

即：给你一个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         else
18         {
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 1
75     {
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 };

View Code

输入：Link()
输出：ans, bool Dance(int k)

重点来了：如何建图？这里选取典型例题说明

(因为之前丢了一次稿，未完待续)