浅谈DLX
钱逸凡
2018-07-06 13:08:21
DLX又称dancing links X 是一种
### 解决重复覆盖和精确覆盖的高效算法
# 精确覆盖的定义：
一个全集S有若干个子集S1，S2，……Sn，选取其中若干个子集，使得这些集合中出现了S中每个元素各一次。
这么说可能有点抽象（我知道我语文不好），举个例子：
全集S=｛1，2，3，4，5，6，7｝，
用子集S1=｛1，2，3｝，S2=｛3，4，5，7｝，S3=｛4，5，6，7｝，S4=｛1，5，6，7｝，S5={4,5}精确覆盖，结果显然是选取S1和S3。
# 主要思想：
把全集中的每个元素对应成一个矩阵中的列，把每个子集对应成一个行
对于矩阵中一点（i，j）若集合Si包含元素j则改点为1，否则为0。
我表达能力确实不行，将就看吧，实在不行就看图吧。~~（蒟蒻不会绘图软件，只好手敲了）~~
还是刚才的例子，矩阵表示为：
S | 1 |2 |3 |4 |5 |6 |7
S1 | 1 |1 |1 |0 |0 |0 |0
S2 | 0 |0 |1 |1 |1 |0 |1
S3 | 0 |0 |0 |1 |1 |1 |1
S4 | 1 |0 |0 |0 |1 |1 |1
S5 | 0 |0 |0 |1 |1 |0 |0
接下来是核心操作：
先选取一个集合（一行），把该行和该行上有点的列和包含这些列的行删除（还是看图吧……），比如说我们选了第1行：
S | 4 |5 |6 |7
S3 | 1 |1 |1 |1
S5 | 1 |1 |0 |0
为什么是这样呢？首先我们要知道当我们把矩阵删完后就完成了精确覆盖，我们选了第一行所以第一行中的元素对应的列就删完了，而包含了这些元素的行肯定是不能选的，所以我们把它们也删了。
接下来如果我们选择了S3，显然矩阵为空，我们找到了一组解，但若我们选择了S5则矩阵变为：
S | 6 |7
矩阵未覆盖完但已经无集合可用，覆盖失败，于是要回溯，于是矩阵又为：
S | 4 |5 |6 |7
S3 | 1 |1 |1 |1
S5 | 1 |1 |0 |0
大致是这样一个过程，具体怎么操作就看代码：
# 代码实现：
首先要知道我们需要的数组和对应的含义：
```
int n,m,cnt;//矩阵的长，宽，点的数量
int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//每个点的左，右，上下，行，列信息
int h[mx];//每行的头结点
int s[mx];//每列的结点数
int ans,ansk[mx];//需要ans个子集，分别为ansk[]
```
dancing links 的原理是十字链表的删除和恢复很方便，利用十字链表来储存我们需要的信息。
1. 第一步 ：建立空的矩阵：
```
void init(int _n,int _m) {
n=_n,m=_m;
int i;
for(i=0; i<=m; i++) {
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;//m右边是0
l[0]=m;//0左边是m
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;//开始时有m个结点（0结点和各列头结点）
}//初始化，生成每列的头
```
1. 第二步：在r行c列插入点
```
inline void link(int R,int C) {
s[C]++;
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;//十字链表原理
if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;//该行没有别的点,把第一个加入的点作为该行的行头结点
else {
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
}
```
1. 第三步：删除与恢复：
```
inline void remove(int c) {
r[l[c]]=r[c],l[r[c]]=l[c];
for(int i=d[c]; i!=c; i=d[i]) {
for(int j=r[i]; j!=i; j=r[j]) {
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
}//删除c列和c列上有点的行
inline void resume(int c) {
for(int i=u[c]; i!=c; i=u[i]) {
for(int j=l[i]; j!=i; j=l[j]) {
u[d[j]]=j;
d[u[j]]=j;//十字链表的恢复原理，可以自己画图验证。
s[col[j]]++;
}
}
r[l[c]]=c;
l[r[c]]=c;
}//恢复c列和c列上有点的行，恢复与删除很像
```
1. 第四步：核心dance：
```
bool dance(int deep) {
if(r[0]==0) { //矩阵已经删除完
ans=deep;
//如果要求输出具体的解，可在此处操作（把ansk转换换回对应的集合信息）
return 1;//多解问题去掉这行
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
remove(c);
for(int i=d[c];i!=c;i=d[i]){
ansk[deep]=row[i];
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
if(dance(deep+1)==1)return 1;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
}
resume(c);
return 0;
}
```
推荐几道精确覆盖的题：
[八皇后](https://www.luogu.org/problemnew/show/P1219)
[靶形数独](https://www.luogu.org/problemnew/show/P1074)
注意没有精确覆盖的模版题，要自己转换，把一些条件转换成对应的集合。
没有思路的看看题解[八皇后题解](https://www.luogu.org/blog/ONE-PIECE/solution-p1219)（~~中文不好看完别吐）~~
。靶形数独已经有大佬写的题解了，我就不再献丑了，有需要可以看一下我的代码[靶形数独代码](https://www.luogu.org/blog/ONE-PIECE/ba-xing-shuo-du-dai-ma)
差点忘了，还有重复覆盖。
# 重复覆盖定义：
顾名思意，与精确覆盖差不多，只是可以有元素重复
主要思想：同上（精确覆盖）
## 代码实现：
删除和恢复略有不同
```
inline void del(int c){
for(int i=d[c];i!=c;i=d[i]){
l[r[i]]=l[i],r[l[i]]=r[i];
}
}//删除c列
inline void res(int c){
for(int i=u[c];i!=c;i=u[i]){
l[r[i]]=i,r[l[i]]=i;
}
}//恢复c列
```
dance 部分多了一个剪枝,因为重复覆盖比精确覆盖慢。
```
inline int leave(){
int ans=0;
bool vis[m];
register int i,j,k;
memset(vis,0,sizeof(vis));
for(i=r[0];i!=0;i=r[i]){
if(vis[i]==0){
vis[i]=1;
ans++;
for(j=d[i];j!=i;j=d[j]){
for(k=r[j];k!=j;k=r[k])
vis[col[k]]=1;
}
}
}
return ans;
}//最优情况还要多少个集合
void dance(int deep){
//注意：这个剪枝只有在多解情况求最优解时下才用
if(deep+leave()>=out)return;//剪枝
if(r[0]==0){
out=deep;
return;
}
int c=r[0];
register int i,j;
for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
for(i=d[c];i!=c;i=d[i]){
del(i);
for(j=r[i];j!=i;j=r[j])del(j);
dance(deep+1);
for(j=l[i];j!=i;j=l[j])res(j);
res(i);
}
return;
}//可以看出重复覆盖的效率并不算太高，与深搜差不多，甚至如果深搜剪枝剪得好比dancing links快，谨慎使用
```
洛谷上没找到重复覆盖的题，推荐一道：神龙的难题。
想做的自己去百度
# 万分感谢你们忍着看完了~~这么烂的语文水平写的文章~~
~~祝各位NOIP满分~~
### ~~行行好给个赞吧~~
再附上次模板题的代码：
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=250501;//n*m+m<=250500
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int n,m;
int cnt;
int l[mx],r[mx],u[mx],d[mx],col[mx],row[mx];//每个点的左右上下指针，所在行列
int h[mx];//每行的头结点
int s[mx];//每列的节点数
int ansk[mx];//选了那些集合
void init(int m){//m个元素
for(register int i=0;i<=m;i++){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;
}//初始化
inline void link(int R,int C){//R行C列插入点
s[C]++;
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
if(h[R]==-1)h[R]=r[cnt]=l[cnt]=cnt;//该行没有点，直接加入
else{
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
return;
}
inline void remove(int C){//删除涉及C列的集合
r[l[C]]=r[C],l[r[C]]=l[C];
for(int i=d[C];i!=C;i=d[i]){
for(int j=r[i];j!=i;j=r[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
}
inline void resume(int C){//恢复涉及C列的集合
for(int i=u[C];i!=C;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
r[l[C]]=C;
l[r[C]]=C;
}
bool dance(int deep){
if(r[0]==0){
register int i=0;
for(i=0;i<deep;i++)printf("%d ",ansk[i]);
return 1;
}
int c=r[0];
int i,j;
for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
remove(c);
for(i=d[c];i!=c;i=d[i]){
ansk[deep]=row[i];
for(j=r[i];j!=i;j=r[j])remove(col[j]);
if(dance(deep+1))return 1;
for(j=l[i];j!=i;j=l[j])resume(col[j]);
}
resume(c);
return 0;
}
int main(){
// freopen("cin.txt","r",stdin);
n=Read(),m=Read();
register int i,j;
int f;
init(m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
f=Read();
if(f)link(i,j);
}
}
if(!dance(0))printf("No Solution!");
return 0;
}
```