求助DLX模板!
查看原帖
求助DLX模板!
230394
wqqe223楼主2021/10/30 15:54
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=508;
const int INF=0x3fffffff;
struct node
{
	int r,c,siz;
	node *up,*down,*left,*right;
};
node *col[N],*row[N],*rec[N][N];
int arr[N],book[N],b1[N];
node *head;
inline void init(int r,int c)
{
	head=(node*)malloc(sizeof(node));
	head->r=head->c=0;
	head->left=head->right=head->down=head->up=head;
	for(int i=1;i<=c;i++)
	{
		col[i]=(node*)malloc(sizeof(node));
		col[i]->r=0,col[i]->c=i;
		col[i]->up=col[i]->down=col[i];
		col[i]->left=head->left,col[i]->right=head;
		col[i]->left->right=col[i]->right->left=col[i];
		col[i]->siz=0;
	}
	for(int i=1;i<=r;i++)
	{
		row[i]=(node*)malloc(sizeof(node));
		row[i]->c=0,row[i]->r=i;
		row[i]->left=row[i]->right=row[i];
		row[i]->up=head->up,row[i]->down=head;
		row[i]->up->down=row[i]->down->up=row[i];
	}
}
inline void delLR(node* a){a->left->right=a->right,a->right->left=a->left;}
inline void recLR(node* a){a->left->right=a,a->right->left=a;}
inline void delUD(node* a){a->up->down=a->down,a->down->up=a->up;}
inline void recUD(node* a){a->up->down=a,a->down->up=a;}
inline void addnode(int r,int c)
{
	rec[r][c]=(node*)malloc(sizeof(node));
	rec[r][c]->r=r,rec[r][c]->c=c;
	rec[r][c]->up=col[c]->up,rec[r][c]->down=col[c];
	rec[r][c]->left=row[r]->left,rec[r][c]->right=row[r];
	rec[r][c]->down->up=rec[r][c]->up->down=rec[r][c]->left->right=rec[r][c]->right->left=rec[r][c];
	col[c]->siz++;
}
inline void cover(int c)
{
	delLR(col[c]);
	for(node* i=col[c]->down;i!=col[c];i=i->down)
	{
		for(node* j=row[i->r]->right;j!=row[i->r];j=j->right)
		{
			if(j->c==c)continue;
			delUD(rec[i->r][j->c]);
			col[j->c]->siz--;
		}
	}
}
inline void recover(int c)
{
	for(node* i=col[c]->up;i!=col[c];i=i->up)
	{
		for(node* j=row[i->r]->left;j!=row[i->r];j=j->left)
		{
			if(j->c==c)continue;
			recUD(rec[i->r][j->c]);
			col[j->c]->siz++;
		}
	}
	recLR(col[c]);
}
inline bool Algorithm_X(int dep)
{
	if(head->right==head)
	{
		for(int i=1;i<dep;i++)
			cout<<arr[i]<<" ";
		return true;
	}
	int c=0,minn_siz=INF;
	for(node* i=head->right;i!=head;i=i->right)
	{
		if(i->siz<minn_siz)
		{
			c=i->c;
			minn_siz=i->siz;
		}
	}
	cover(c);
	for(node* i=col[c]->down;i!=col[c];i=i->down)
	{
		for(node* j=row[i->r]->right;j!=row[i->r];j=j->right)
		{
			if(j->c==c)continue;
			cover(j->c);
		}
		arr[dep]=i->r;
		if(Algorithm_X(dep+1))return 1;
		for(node* j=row[i->r]->left;j!=row[i->r];j=j->left)
		{
			if(j->c==c)continue;
			recover(j->c);
		}
	}
	recover(c);
	return false;
}
int main()
{
	freopen("test.in","r",stdin);
	int n,m;
	cin>>n>>m;
	init(n,m);
	int num;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>num;
			if(num)addnode(i,j);
		}
	}
	if(!Algorithm_X(1)){puts("No Solution!");}
	fclose(stdin);
	return 0;
}

WA+RE,求助。

2021/10/30 15:54
加载中...