浅谈DancingLinksX算法
前置知识：
⼀维链表。（单向，双向，循环）
部分集合运算，如 \(\bigcap\)，\(\bigcup\).
前⾔
在计算机科学中，X算法可⽤来求解精确覆盖问题。
精确覆盖问题是哪⼀类问题呢？ \(X\) 算法⼜是什么⾼深的算法呢？
背景
你的同学通过某种算法迅速 \(\text{AC}\) 了，然后他兴致勃勃地带领学⽣ \(1s\) 搞定数独竞赛。
⼩时候，你玩数独；长⼤了，数独玩你。你该怎么办？
那位同学⽤ \(\text{DLX}\) 轻松码⼒全开搞定了
⼩时候，你玩智慧珠；长⼤了，智慧珠玩你。你该怎么办？
定义
\(\text{Dancing Links X}\) 是优化后的 \(X\) 算法，⽤于解决精确覆盖问题。
精确覆盖问题是这样⼀类问题：给定若⼲集合 \(S_1 , S_2 \cdots S_n\) 和⼀个集合 \(X\)，求出 \(T1 , T2 \cdots T_k\) 使得满⾜：
\[T_i \bigcap T_j = \varnothing (i \not = j) \]
\[\bigcup_{i=1}^k T_i = X \]
\[∀ i \in [1,k] , T_i \in {S_1 , S_2 \cdots S_n} \]
翻译成⼈话其实就是在 \(n\) 个集合中选出若⼲两两不相交的集合且这些集合的并为 \(X\).
⽐⽅说：
\[S_1 = {666,2,4} \]
\[S_2={2,4,8,119} \]
\[S_3={8,5} \]
\[S_4={666,2,4,119} \]
\[S_5={666,4,5} \]
\[X={666,2,8,4,5,119} \]
那么这时答案就应该是取 \(S_4\) 和 \(S_3\).
那么，如何解决这类问题呢？
算法⼀
暴⼒搜索解决问题。
我们⽤ \(2^n\) 的时间枚举每个集合是否被选择。然后 \(O(n)\) 验证即可。
时间复杂度：\(O(2^n \times nm)\).（\(m\) 为 \(\bigcup_{i=1}^n S_i\) 的⼤⼩）
算法⼆
不得不说算法⼀时间⽆法承受。
我们⾸先将 \(S\) 与 \(X\) 离散化，并构造矩阵 \(a (n \times m)\) ，其中 \(a_{i,j}\) 表⽰ \(S_i\) 是否含有离散化后的 \(j\)；\(m\) 为 \(\bigcup_{i=1}^n S_i\) 的⼤⼩。
那么，对上述问题建矩阵可得：
\[\begin{Bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ \end{Bmatrix} \]其中 \(1\) ~ \(6\) 列分别表⽰：\(\in 666 , \in 2 , \in 8 , \in 4 , \in 5 , \in 119\).
问题转化为：求 \(01\) 矩阵选出若⼲⾏，使得每列有且只有 \(1\) 个 \(1\).
printf输出格式 同行
考虑将每⾏看做⼀个⼆进制数，即要求所有选出⾏的或为 \(2^m-1\)，且任意两个数的与为 \(0\).
⽤⼀个变量记录当前或值，然后计算即可。
时间复杂度：\(O(2^n \times n)\).
算法三
考虑 \(X\) 算法。回顾⼀下这个图：
\[\begin{Bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ \end{Bmatrix} \]⾸先我们选择第⼀⾏，然后把第⼀⾏的 \(1\) 所在列标记，把所有被标记的列上有 \(1\) 的那⼀⾏删除。得到：
绿⾊表⽰标记的列，红⾊表⽰当前⾏，紫⾊表⽰被删除的⾏。
为什么呢？因为当前列有了 \(1\)，别的列不能再有了；有的肯定不能选，删除它们是⼀个有⼒的剪枝。
然后你发现你只能选第 \(3\) ⾏，验证后发现第 \(6\) 列没有 \(1\)，所以回溯，不选第 \(1\) ⾏。回溯之前，需要恢复之前删掉的⾏。
注：图上 \(a_{2,2}\) 忘记标了，不过第 \(1\) ⾏不在我们考虑的范围内（已经确定不能选了），不会影响结果；但忘记标了可能会影响理解，⼤家谅解⼀下。
当然，这⾥如果为了⽅便理解把第⼀⾏删去也是可以的。
然后同理，你发现第 \(2\) ⾏选了之后⽆⾏可选。（因为前⾯的搜索已经确定了第 \(1\) ⾏选了⽆解，所以不选）
验证，发现第 \(1\) 列没有选 \(1\) （后⾯的不⽤再看，⼀列⽆解就是⽆解了），直接回溯，说明第 \(2\) ⾏也不能选，恢复删除⾏。
然后选第 \(3\) ⾏。
咦？你发现可以递归下去选第 \(4\) ⾏。
验证发现正确！
所以得到答案：\(S_3 , S_4\)，退出搜索。
所以，\(X\) 算法的步骤⼤致为：
1. 对当前矩阵删除当前⾏，并删去与当前⾏有公共元素（即同列有 \(1\)）的所有⾏，递归下⼀层。
2. 如果所有⾏返回⽆解即返回⽆解给上⼀层，并恢复⾏，回到第 \(1\) 步。
3. 如果发现所有列都被标记则输出答案，结束搜索。
4. 所有搜索⽆解则返回⽆解。
你发现，该搜索需要⼤量的删除⾏，恢复⾏的操作。
⽽ \(X\) 算法的时间复杂度是指数级的，其回溯、搜索层数取决于矩阵中 \(1\) 的个数⽽不是 \(n\) 或者 \(m\) 的⼤⼩。其时间复杂度⼤概可以接受 \(n,m \leq 100\) 的情况。
算法四
\(\text{Dancing Links 意为：跳舞的链}\)
为什么叫做跳舞的链呢？是这样的。
假设我们要写这样⼀道题⽬：
给定⼀个 \(n \times m\) 的⼆维矩阵，你需要⽀持 \(q\) 个操作：
1. 删除第 \(x\) ⾏；
2. 查询 \(a_{i,j}\) 的值。
数据范围：\(n,m \leq 500\)，\(q \leq 10^5\).
当然如果你暴⼒删除的话，时间复杂度是 \(O(n \cdot m \cdot q)\).
但是我们想⼀个弱化版：
给定⼀个长为 \(n\) 的数组，你需要⽀持 \(q\) 个操作：
1. 删除第 \(x\) 个数；
2. 查询第 \(a_i\) 的值。
数据范围：\(n \leq 500\)，\(q \leq 10^5\).
这直接⽤⼀维链表弄⼀下就可以了是不？
所以，⼀个叫 \(\texttt{Donald E. Knuth}\) 的计算机科学家，发明了 “⼗字链表” 解决此类问题。
⼗字链表的图⼤概是这样的：
（下⾯⼗字链表的图，代码思路摘⾃）
似乎⾮常简单的样⼦，那再给⼀张：
说⽩了你第⼀眼看到我也是这个感觉：
别扯了，说正题。回到这个图：
每个节点弄个指针指向它上下左右的节点，然后再开数组记录每⾏，每列的元素个数。 \(fir_i\) 是我们在每⾏链表之前虚构的⼀个元素，每次从它开始遍历。
STEP 1
#define FOR(i,A,x) for(int i=A[x];i!=x;i=A[i])
预处理优化宏定义都好⽤
定义数组。
int n,m,id,fir[N],siz[N];
int L[N],R[N],U[N],D[N];
int col[N],row[N],ans;
int stk[N]; //stk 记录答案
STEP 2
如何建⽴⼀个 \(n \times m\) 的 \(\text{Dancing Link？}\) 很显然，对于⼀⾏是这样的：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。