luogu P4929 【模板】舞蹈链 DLX

LINK：舞蹈链

具体复杂度我也不知道但是搜索速度极快.

原因大概是因为每次检索的时间少有一定的剪枝.

花了2h大概了解了这个东西吐槽一下题解根本看不懂只能理解大概的想法核心的链表不太懂.

于是直接看代码了应该算是把代码给理解了于是就懂了链表是怎么操作的。

首先对于列先建立一个循环链表 r[0]==0时说明所有的列被填完.

没必要建立0的点因为没有什么用只需要知道1在哪即可。

对于1的结点新建结点然后这些结点组成一个双向十字链表注意和上面那个循环链表不连在一起.

这个循环链表容易建立值得一提的是需要检索列的链表所以需要在列的链表头处加一个标号使得能够找到.

而横排则不需要直接利用列就可以找到.

下面是删除.

找到一列之后随便找一行删除当前行同时意味着当前行上所有1的位置所在列被删掉.

考虑删掉列的操作这些列所在的行要被删掉所以再枚举行删掉列.

回溯的时候也很容易还原.

这样进行搜索即可.

理解海星下次再加深理解好了.

const int MAXN=5510;

int n,m,cnt,ans;

int ans1[MAXN];

int l[MAXN],r[MAXN],col[MAXN],row[MAXN],u[MAXN],d[MAXN],h[MAXN],s[MAXN];

inline void prepare()

{

	rep(0,m,i)

	{

		r[i]=i+1;

		l[i]=i-1;

		u[i]=d[i]=i;

	}

	r[m]=0;l[0]=m;

	memset(h,-1,sizeof(h));

	memset(s,0,sizeof(s));

	cnt=m+1;

}

inline void Link(int x,int y)

{

	++s[y];//某一列的结点个数.

	row[cnt]=x;col[cnt]=y;

	u[cnt]=y;d[cnt]=d[y];//显然这个地方是纵向循环链表.

	u[d[y]]=cnt;d[y]=cnt;

	if(h[x]==-1)h[x]=r[cnt]=l[cnt]=cnt;

	else

	{

		r[cnt]=h[x];//显然这个地方是横向循环链表.

		l[cnt]=l[h[x]];//容易得到h[x]表示当前行的首结点 同时也是末结点.

		r[l[h[x]]]=cnt;

		l[h[x]]=cnt;

	}

	++cnt;

}

inline void remove(int y)

{

	r[l[y]]=r[y];l[r[y]]=l[y];

	for(int i=d[y];i!=y;i=d[i])

	{

		for(int j=r[i];j!=i;j=r[j])

		{

			u[d[j]]=u[j];

			d[u[j]]=d[j];

			--s[col[j]];

		}

	}

}

inline void resume(int y)

{

	for(int i=u[y];i!=y;i=u[i])

	{

		for(int j=l[i];j!=i;j=l[j])

		{

			u[d[j]]=j;

			d[u[j]]=j;

			++s[col[j]];

		}

	}

	r[l[y]]=y;l[r[y]]=y;

}

inline void dance(int dep)

{

	if(r[0]==0)

	{

		rep(1,dep-1,i)put_(ans1[i]);

		exit(0);

	}

	int y=r[0];

	for(int i=r[0];i;i=r[i])if(s[i]<s[y])y=i;

	remove(y);

	for(int i=d[y];i!=y;i=d[i])

	{

		ans1[dep]=row[i];

		for(int j=r[i];j!=i;j=r[j])remove(col[j]);

		dance(dep+1);

		for(int j=l[i];j!=i;j=l[j])resume(col[j]);

	}

	resume(y);

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);prepare();

	rep(1,n,i)

	{

		rep(1,m,j)

		{

			int get(op);

			if(op)Link(i,j);

		}

	}

	dance(1);puts("No Solution!");

	return 0;

}

巴特西

luogu P4929 【模板】舞蹈链 DLX

最新文章

热门文章