CoinciDANCE——DLX学习笔记

为了优雅地解决数独问题，我找到了优雅的Dancing Links。

DLX（Dancing Links + X Algorithm）简介

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[]

2. 在R行C列插入点

inline void link(int R,int C) {
		s[C]++;//第C列总的节点数+1
		row[cnt]=R;//该节点在第R行
		col[cnt]=C;//该节点在第C列
		u[cnt]=C;//它的上面节点编号是C
		d[cnt]=d[C];//它的下面节点编号是d[C]
		u[d[C]]=cnt;//d[C]的上面是当前节点cnt
		d[C]=cnt;//C的下面是cnt
//相当于在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++;
	}

My模板code

洛谷P4929 【模板】舞蹈链（DLX）
AC 47ms

#include
using namespace std;
const int N=5510;
int n,m,a;
int u[N],d[N],l[N],r[N],row[N],col[N],cnt;
int sv[N],hd[N],ans[N],dep;

inline int read() {
	register int x=0,f=0;
	char ch=getchar();
	while(ch<'0' || ch>'9') {
		if(ch=='-') f=1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f? -x : x;
}

inline void rec(int c) {
	register int i,j;
	for(i=u[c]; i!=c; i=u[i]) {
		for(j=l[i]; j!=i; j=l[j]) {
			u[d[j]]=d[u[j]]=j;
			sv[col[j]]++;
		}
	}
	r[l[c]]=l[r[c]]=c;
}

inline void rem(int c) {
	l[r[c]]=l[c];
	r[l[c]]=r[c];
	register int i,j;
	for(i=d[c]; i!=c; i=d[i]) {
		for(j=r[i]; j!=i; j=r[j]) {
			u[d[j]]=u[j];
			d[u[j]]=d[j];
			sv[col[j]]--;
		}
	}
}

bool dance(int tmp) {
	if(!r[0]) {
		dep=tmp;
		return true;
	}
	register int c=r[0],i,j;
	for(i=r[0]; i!=0; i=r[i]) {
		if(sv[i]