DLX10pts求调【玄关】
查看原帖
DLX10pts求调【玄关】
780539
qwertim楼主2023/10/20 09:10
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
struct node{int x,y,left,right,up,down;}dlx[5505];
int n,m,ans[505],cnt,x_0_1,r[505],c[505];
void init(){
	fo(i,0,m){
		dlx[i].left=(!i?m:i-1),dlx[i].right=(i==m?0:i+1);
		dlx[i].up=dlx[i].down=i,dlx[i].y=i;
	}
	cnt=m;
}
void add(int X,int Y){
	cnt++;
	dlx[cnt].x=X,dlx[cnt].y=Y;
	dlx[cnt].up=dlx[Y].up,dlx[dlx[cnt].up].down=cnt,dlx[cnt].down=Y;
	dlx[Y].up=cnt;
	if(!r[X])dlx[cnt].left=dlx[cnt].right=cnt,r[X]=cnt;
	else{
		dlx[cnt].left=dlx[r[X]].left,dlx[cnt].right=r[X];
		dlx[dlx[cnt].left].right=dlx[dlx[cnt].right].left=cnt;
	}
	c[Y]++;
}
void del_line(int C){
	for(int i=dlx[C].down,j=i;i!=C;i=j=dlx[i].down){
		if(dlx[i].x==0)continue;
		do{
			dlx[dlx[j].up].down=dlx[j].down;
			dlx[dlx[j].down].up=dlx[j].up;
			c[dlx[j].y]--;
			j=dlx[j].right;
		}while(j!=i);
	}
}
void re_add_line(int C){
	for(int i=dlx[C].down,j=i;i!=C;i=j=dlx[i].down){
		if(dlx[i].x==0)continue;
		do{
			dlx[dlx[j].up].down=dlx[dlx[j].down].up=j;
			c[dlx[j].y]++;
			j=dlx[j].right;
		}while(j!=i);
	}
}
bool Dancing_Links(int num){
	if(!dlx[0].right){
		fo(i,1,num-1)cout<<ans[i]<<' ';
		return 1;
	}
	int C=dlx[0].right;
	for(int i=dlx[0].right;i;i=dlx[i].right)C=(c[i]<c[C]?i:C);
	dlx[dlx[C].left].right=dlx[C].right,dlx[dlx[C].right].left=dlx[C].left;
	for(int i=dlx[C].down,j=i;i!=C;i=j=dlx[i].down){
		ans[num]=dlx[i].x;
		do{del_line(j);j=dlx[j].right;}while(j!=i);
		if(Dancing_Links(num+1))return 1;
		do{re_add_line(j);j=dlx[j].left;}while(j!=i);
	}
	dlx[dlx[C].left].right=dlx[dlx[C].right].left=C;
	return 0;
}
int main(){
	cin>>n>>m;
	init();
	fo(i,1,n)
		fo(j,1,m){
			cin>>x_0_1;
			if(x_0_1)add(i,j);
		}
	if(!Dancing_Links(1))cout<<"No Solution!";
	return 0;
}
2023/10/20 09:10
加载中...