DLX

notes

概述

神秘的搜索优化？

【模板】舞蹈链（DLX）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int N=500+10,M=6e3+100;
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,a[N][N],col[M],cow[M],siz[N],head[N],U[M],D[M],L[M],R[M],tot=0,sta[N],tp=0;

void bui(int n,int m){ for(int i=0;i<=m;++i) L[i]=(i==0?m:i-1),R[i]=(i==m?0:i+1),U[i]=D[i]=i; tot=m; }
void ins(int x,int y){
	D[++tot]=D[y],U[tot]=y,U[D[y]]=tot,D[y]=tot,cow[tot]=x,++siz[col[tot]=y];
	if(!head[x]) head[x]=L[tot]=R[tot]=tot;
	else R[tot]=R[head[x]],L[tot]=head[x],L[R[head[x]]]=tot,R[head[x]]=tot;
}
void del(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],--siz[col[j]];
}
void rev(int c){
	R[L[c]]=L[R[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]]=D[U[j]]=j,++siz[col[j]];	
}
int dance(){
	if(!R[0]) return 1;
	int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(siz[i]<siz[c]) c=i;
	del(c);
	for(int i=D[c];i!=c;i=D[i]){
		sta[++tp]=cow[i];
		for(int j=R[i];j!=i;j=R[j]) del(col[j]);
		if(dance()) return 1; --tp;
		for(int j=L[i];j!=i;j=L[j]) rev(col[j]);
	}
	rev(c);
	return 0;
}

int main(){
	
	n=rd,m=rd,bui(n,m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(rd) ins(i,j);
	
	if(!dance()) return printf("No Solution!\n"),0;
	for(int i=1;i<=tp;++i) printf("%d ", sta[i]);
	
	return 0;
}

例题

1.数独

$(x,y,z)$ 三元组，表示 $(x,y)$ 填 $z$。那么限制有

  • 每行数不重复

  • 每列数不重复

  • 每宫数不重复

  • 每格数不重复

有 $9^3=729$ 个三元组，限制需要 $4 \times 9^2=324$ 位，总共有 $3 \times 729=2187$ 个 $1$。

2.[NOIP2009 提高组] 靶形数独

1
2
3
4
5
6
7
8
9
10
11
12
const int val[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}
};

3.[NOI2005] 智慧珠游戏

用五元组表示一次操作，即类型，位置，旋转次数，是否翻转。
限制是

  • 位置被占

  • 珠子被占

最终所有位置与珠子都要被占。

参考

DLX