舞蹈链(DLX)

精确覆盖问题の定义

精确覆盖问题(英文:Exact Cover Problem)是指给定许多集合 \(S_i (1 \le i \le n)\) 以及一个集合 \(X\),求满足以下条件的无序多元组 \((T_1, T_2, \cdots , T_m)\)

  1. \(\forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j)\)
  2. \(X = \bigcup\limits_{i = 1}^{m}T_i\)
  3. \(\forall i \in[1, m], T_i \in \{S_1, S_2, \cdots, S_n\}\)

P4929 【模板】舞蹈链(DLX)

写的很好的题解!

OI wiki~

\(My \space Code\)

#include<bits/stdc++.h>
#define il inline
#define ri register
#define pc(i) putchar(i)
#define cs const
using namespace std;
namespace zxyc
{
	il void read(int &as)
	{
		as=0;int f=1;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
		while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
	}
	void wt(int x){if(x<0) x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
}using namespace zxyc;
struct DLX{int row,col,l,r,u,d;}mp[6003];
int cnt,rowf[503],ans[503],colc[503],n,m;
//rowf每行第一个元素 colc[510]每列元素个数
il void init()
{
	for(ri int i=0;i<=m;++i)
		mp[i].l=i-1,mp[i].r=i+1,mp[i].u=mp[i].d=i,colc[i]=0;
	mp[0].l=m,mp[m].r=0,cnt=m;
}
il void add(cs int r,cs int c)
{
	//upd:col
	mp[++cnt].row=r,mp[cnt].col=c,
	mp[cnt].u=mp[c].u,mp[cnt].d=c,
	mp[mp[cnt].u].d=cnt,mp[c].u=cnt;
	//upd:row
	if(!rowf[r]) mp[cnt].l=mp[cnt].r=cnt,rowf[r]=cnt;
	else mp[cnt].l=mp[rowf[r]].l,mp[cnt].r=rowf[r],
		mp[mp[cnt].l].r=mp[mp[cnt].r].l=cnt;
	colc[c]++;
}
il void remove(cs int c)
{
	for(ri int i=mp[c].d;i!=c;i=mp[i].d)
		for(ri int j=mp[i].r;j!=i;j=mp[j].r)
			mp[mp[j].d].u=mp[j].u,mp[mp[j].u].d=mp[j].d,colc[mp[j].col]--;
	mp[mp[c].r].l=mp[c].l,mp[mp[c].l].r=mp[c].r;	
} 
il void resume(cs int c)
{
	mp[mp[c].l].r=c,mp[mp[c].r].l=c;
	for(ri int i=mp[c].d;i!=c;i=mp[i].d)
		for(ri int j=mp[i].r;j!=i;j=mp[j].r)
			mp[mp[j].d].u=j,mp[mp[j].u].d=j,colc[mp[j].col]++;
}
bool dance(cs int step)
{
	if(mp[0].r==0)
	{
		for(ri int i=1;i<step;++i) 
			wt(ans[i]),pc(' ');
		return true;
	}
	int C=mp[0].r;//选择列中元素最少的列
	for(ri int i=mp[0].r;i;i=mp[i].r) 
		if(colc[i]<colc[C]) C=i;
	remove(C);
	for(ri int i=mp[C].d;i!=C;i=mp[i].d)
	{
		ans[step]=mp[i].row;
		for(ri int j=mp[i].r;j!=i;j=mp[j].r)
			remove(mp[j].col);
		if(dance(step+1)) return true;
		for(ri int j=mp[i].r;j!=i;j=mp[j].r)
			resume(mp[j].col);
	}
	return resume(C),false;
	
 } 
signed main()
{
	read(n),read(m),init();
	for(ri int i=1;i<=n;++i)
		for(ri int j=1,x;j<=m;++j)
			{read(x);if(x) add(i,j);}
	if(!dance(1)) puts("No Solution!");		
	return 0;
 } 

原文链接: https://www.cnblogs.com/Bertidurlah/p/17053093.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    舞蹈链(DLX)

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/312300

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月16日 下午12:20
下一篇 2023年2月16日 下午12:20

相关推荐