Dancing Links X
概述
用来解决精确覆盖问题。
给定集合\(X\)与集合的集合\(S\)
求\(T \subseteq S\)使得
\[\bigcap_{A \in T} A = \empty \\bigcup_{A \in T} A = X
\]
X算法
先转化为矩阵:矩阵\((i, j)\)位置为1当且仅当\(X_j \in S_i\)，否则为0
然后我们每次按1的个数从小往大枚举选择的行，那么这一行为1的位置对应的列上为1的位置的行都要删去，这些列也应删去。然后重复上述过程。
最后一次删除的行如果是满的则找到一个解，否则就继续枚举。
Dancing Links X
可以预见上述算法有优化的余地。
这时就该请出双向十字循环链表了，链表能向上走、向下走、向左走、向右走走到下一个为1的位置。同时每行每列都有指针指向起始位置。
发现这种数据结构能够帮助我们优化删除矩阵行列的时间。
虽然还是指数级别的时间。这种东西只有\(O(TLE)\)和\(O(Not\ TLE)\)吧