舞蹈链（DLX）精确覆盖问题

本文主要是介绍舞蹈链（DLX）精确覆盖问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

DLX 是 NOIWC2022 讲的一个算法，然后我一直咕咕咕到了现在。

板子题

题目传送门
题目大意：
给定一个 01 矩阵，在这个矩阵中选出若干行，使得在选出的行中，每一列恰好有 \(1\) 个 \(1\)。
矩阵行列 \(N,M\) 范围为 \(N,M\le 500\)，矩阵中 \(1\) 的个数 \(\le 5000\)。

题目解析

其实这就是精确覆盖问题。
精确覆盖的定义是：一个全集 \(S\) 有若干个子集 \(S_1,S_2,\dots,S_n\)，选取其中若干个子集，使得这些集合中出现了 \(S\) 中每个元素各一次。
考虑建模成一个矩阵：设 \(S=\{a_1,a_2,\dots,a_m\}\)每一行代表一个子集，如果这个子集 \(S_i\) 中存在原始 \(a_j\)，那么第 \(i\) 行 \(j\) 列就为 \(1\)，否则为 \(0\)。这样就转化成了前面的板子题。

算法解析

假设 \(N,M\) 同阶。
首先考虑搜索，枚举每一行是否出现，算法复杂度为 \(O\left(2^NN\right)\)，显然会超时。
考虑剪枝，我们发现如果选了第 \(i\) 行，并且这一行中的第 \(j\) 列为 \(1\)，那么第 \(j\) 列为 \(1\) 的所有行都可以不考虑。
这样就可以大致给出算法的主要框架：

1. 如果矩阵为空，就找到了答案；如果矩阵有一列全是 \(0\)，那么就说明当前找到的解是错的，返回。
2. 找到 \(1\) 的个数最少的一列 \(c\)，并且删除这一列。（这样可以再下一步的枚举中枚举次数尽可能少）
3. 枚举第 \(c\) 列中第 \(i\) 行，把第 \(i\) 行计入答案。
4. 对与每一个第 \(i\) 行，删除第 \(i\) 行，然后把第 \(i\) 行中为 \(1\) 的列全部删除。
5. 递归求解新的矩阵。
6. 如果有解就返回并且输出结果，否则第 \(4\) 步恢复删除的行，并且从答案中删除 \(i\)，回到第 \(3\) 步。
7. 如果都没有解，恢复第 \(c\) 列，返回。
   我们发现，在删除的时候我们可以通过 十字双向循环链表 来做到比较快速和方便的删除。

DLX 的算法复杂度和矩阵中 \(1\) 的个数有关，假设 \(1\) 的个数为 \(n\)，那么算法复杂度为 \(O\left(c^n\right)\)，其中 \(c\) 为一个略大于 \(1\) 的常数。

具体代码实现注意：

1. 数组 l,r,u,p,s,row,col 分别代表 左边的点、右边的点、上方的点、下方的点、这一列 \(1\) 的个数、这个点所在的行、这个点所在的列。
2. 注意十字链表的数组大小要考虑加上链表头的点。

代码：

#include<cstdio>
#define db double
#define gc getchar
#define pc putchar
#define U unsigned
#define ll long long
#define ld long double
#define ull unsigned long long
#define Tp template<typename _T>
#define Me(a,b) memset(a,b,sizeof(a))
Tp _T mabs(_T a){ return a>0?a:-a; }
Tp _T mmax(_T a,_T b){ return a>b?a:b; }
Tp _T mmin(_T a,_T b){ return a<b?a:b; }
Tp void mswap(_T &a,_T &b){ _T tmp=a; a=b; b=tmp; return; }
Tp void print(_T x){ if(x<0) pc('-'),x=-x; if(x>9) print(x/10); pc((x%10)+48); return; }
#define EPS (1e-7)
#define INF (0x7fffffff)
#define LL_INF (0x7fffffffffffffff)
#define maxn 5539
#define maxm 539
#define MOD
#define Type int
#ifndef ONLINE_JUDGE
//#define debug
#endif
using namespace std;
Type read(){
	char c=gc(); Type s=0; int flag=0;
	while((c<'0'||c>'9')&&c!='-') c=gc(); if(c=='-') c=gc(),flag=1;
	while('0'<=c&&c<='9'){ s=(s<<1)+(s<<3)+(c^48); c=gc(); }
	if(flag) return -s; return s;
}
int n,m,x,ans[maxn],anscnt;
int s[maxm],l[maxn],r[maxn],u[maxn],d[maxn],row[maxn],col[maxn],head,cnt,findans;
void build(){
	n=read(); m=read(); int i,j,beg,end; head=findans=0;
	for(i=0;i<=m;i++) s[i]=0,l[i]=i-1,r[i]=i+1,u[i]=d[i]=i; l[0]=m; r[m]=0; cnt=m;
	for(i=1;i<=n;i++){
		beg=end=cnt+1;
		for(j=1;j<=m;j++){
			x=read(); if(!x) continue;
			l[++cnt]=end,r[cnt]=beg,l[beg]=cnt,r[end]=cnt,end=cnt; s[j]++;
			d[u[j]]=cnt,u[cnt]=u[j],d[cnt]=j,u[j]=cnt; row[cnt]=i,col[cnt]=j;
		}
	}
}
void del(int x){
	l[r[x]]=l[x],r[l[x]]=r[x]; int i,j;
	for(i=d[x];i!=x;i=d[i]) for(j=r[i];j!=i;j=r[j]) u[d[j]]=u[j],d[u[j]]=d[j],s[col[j]]--;
	return;
}
void rem(int x){
	l[r[x]]=r[l[x]]=x; int i,j;
	for(i=u[x];i!=x;i=u[i]) for(j=l[i];j!=i;j=l[j]) u[d[j]]=d[u[j]]=j,s[col[j]]++;
	return;
}
void dance(){
	if(r[head]==head){ findans=1; return; } int minx=INF,miny,i,j;
	for(i=r[head];i!=head;i=r[i]){
		if(!s[i]) return;
		if(s[i]<minx) minx=s[i],miny=i;
	} del(miny);
	for(i=d[miny];i!=miny;i=d[i]){
		ans[++anscnt]=row[i];
		for(j=r[i];j!=i;j=r[j]) del(col[j]);
		dance(); if(findans) return; anscnt--;
		for(j=l[i];j!=i;j=l[j]) rem(col[j]);
	} rem(miny); return;
}
void print(){
	if(!findans){ puts("No Solution!"); return; }
	int i; for(i=1;i<=anscnt;i++) print(ans[i]),pc(' '); return;
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen(".out","w",stdout);
	build(); dance(); print(); return 0;
}

这篇关于舞蹈链（DLX）精确覆盖问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！