简介
用途：解决精确/重复覆盖问题（某一列含有恰好1个1），全称Dancing Links X，X是未知搜索算法的意思。
洛谷模板题
超详细的算法图解
实际上并不难，就是 暴搜 + 十字链表维护。
把所有的1拿出来建十字链表，枚举每一列被哪一行覆盖，然后去掉跟这一列以及这一行有关的1，递归求解。
每个点记录6个值， l , r , u , d , c o l , r o w l,r,u,d,col,row l,r,u,d,col,row，分别表示左/右/上/下的点，以及它所在的行和列。循环链接。
额外需要一个头 h e a d head head，一排点表示列的代表点 c i c_i ci，第 i i i 列被覆盖就把 c i c_i ci 的两边接起来。如果 r [ h e a d ] = 0 r[head]=0 r[head]=0 则说明所有列都被覆盖了。
d [ c i ] d[c_i] d[ci]指向第 i i i 列的第一个点，第 i i i 列的最后一个点指向 c i c_i ci
删除和恢复顺序相反。
枚举当前列选哪一行时找点数最少的列，减少枚举次数。额外记变量
s
i
s_i
si 表示第
i
i
i 列 1 的个数。
如果某一个
c
i
c_i
ci 还存在但是
s
i
=
0
s_i=0
si=0，说明覆盖不了了，
return
false
\texttt{return~false}
return false
精确覆盖
P4929洛谷模板题
注意空间要开 1 的个数 + 列的长度
下面的代码没有写link，如果写的话因为行的顺序不重要(记录了row)，所以新加一个点可以接在列点的下方。
#include<bits/stdc++.h>
#define maxn 5505
using namespace std;
void read(int &a){
char c;while(!isdigit(c=getchar()));
for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0');
}
int n,m,cnt,l[maxn],r[maxn],u[maxn],d[maxn],s[maxn],col[maxn],row[maxn],ans[maxn];
void remove(int c){//delete 1 linked to the c column
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])
d[u[j]]=d[j],u[d[j]]=u[j],s[col[j]]--;
}
void recover(int c){
for(int i=u[c];i!=c;i=u[i])
for(int j=l[i];j!=i;j=l[j])
d[u[j]]=u[d[j]]=j,s[col[j]]++;
r[l[c]]=l[r[c]]=c;
}
bool dance(int dep){
if(!r[0]){
for(int i=1;i<dep;i++) printf("%d%c",ans[i],i==dep-1?10:32);
return 1;
}
int c=r[0];
for(int i=r[c];i!=0;i=r[i]) if(s[i]<s[c]) c=i;
if(!s[c]) return 0;
remove(c);
for(int i=d[c];i!=c;i=d[i]){
ans[dep]=row[i];
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
if(dance(dep+1)) return 1;
for(int j=l[i];j!=i;j=l[j]) recover(col[j]);
}
recover(c);
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=m;i++) u[i]=d[i]=i,l[i]=i-1,r[i]=i+1;
l[r[m]=0]=cnt=m;
for(int i=1;i<=n;i++)
for(int j=1,hd=0,x;j<=m;j++) if(read(x),x){
s[j]++,cnt++,row[cnt]=i,col[cnt]=j;
if(hd) l[r[cnt]=hd]=r[l[cnt]=cnt-1]=cnt;
else l[cnt]=r[cnt]=hd=cnt;
int pre=u[j];
u[d[cnt]=j]=d[u[cnt]=pre]=cnt;
}
if(!dance(1)) puts("No Solution!");
}
重复覆盖
重复覆盖因为一列可以有多个点，所以删除一列时只需要删去这一列的点，而不再删列上点左右链上的点。而删列的时候要改左右指针，所以删除和恢复的函数和精确覆盖有些不同，不能一开始将一列的左右全改了，而是从选的那一行中横向找1然后删除对应的列。
要删只会完整地删一列， s s s 不会变，开头没有remove也不用判 s [ c ] ≠ 0 s[c]\neq 0 s[c]=0，一开始就会return。
一般求的是最小重复覆盖，需要加上估价函数剪枝。
HDU2295 Radar 题解
Code：
#include<bits/stdc++.h>
#define maxn 3005
using namespace std;
int k,cnt,l[maxn],r[maxn],u[maxn],d[maxn],h[maxn],s[maxn],col[maxn];
void init(int n,int m){
for(int i=0;i<=m;i++) s[i]=0,u[i]=d[i]=i,l[i]=i-1,r[i]=i+1;
l[r[m]=0]=cnt=m;
for(int i=1;i<=n;i++) h[i]=0;
}
void link(int i,int j){
s[col[++cnt]=j]++;
int nxt=d[j]; d[u[cnt]=j]=u[d[cnt]=nxt]=cnt;
if(!h[i]) l[cnt]=r[cnt]=h[i]=cnt;
else {int pre=l[h[i]]; l[r[cnt]=h[i]]=r[l[cnt]=pre]=cnt;}
}
void remove(int i){
for(int j=d[i];j!=i;j=d[j]) l[r[j]]=l[j],r[l[j]]=r[j];
}
void recover(int i){
for(int j=u[i];j!=i;j=u[j]) r[l[j]]=l[r[j]]=j;
}
int E(){
static bool v[maxn]; int ret=0;
for(int i=r[0];i;i=r[i]) v[i]=0;
for(int c=r[0];c;c=r[c]) if(!v[c]){
ret++,v[c]=1;
for(int i=d[c];i!=c;i=d[i])
for(int j=r[i];j!=i;j=r[j])
v[col[j]]=1;
}
return ret;
}
bool dance(int dep){
if(dep+E()>k) return 0;
if(!r[0]) return 1;
int c=r[0];
for(int i=r[c];i!=0;i=r[i]) if(s[i]<s[c]) c=i;
for(int i=d[c];i!=c;i=d[i]){
remove(i);
for(int j=r[i];j!=i;j=r[j]) remove(j);
if(dance(dep+1)) return 1;
for(int j=l[i];j!=i;j=l[j]) recover(j);
recover(i);
}
return 0;
}
const int N = 55;
struct node{int x,y;}a[N],b[N];
int n,m,dis[N*N],id[N*N];
bool cmp(int i,int j){return dis[i]<dis[j];}
int main()
{
int T; scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
dis[(i-1)*m+j]=(a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y);
for(int i=1;i<=n*m;i++) id[i]=i; sort(id+1,id+1+n*m,cmp);
int l=1,r=n*m,mid;
while(l<r){
mid=(l+r)>>1;
init(m,n);
for(int i=1;i<=mid;i++) link((id[i]-1)%m+1,(id[i]-1)/m+1);
if(dance(0)) r=mid;
else l=mid+1;
}
printf("%.6f\n",sqrt(dis[id[l]]));
}
}
