DLX板子,90ptsTLEon#6求调教
查看原帖
DLX板子,90ptsTLEon#6求调教
754502
_AyachiNene楼主2023/5/27 17:26
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int x,y,u,d,l,r;
}a[114514*3];
int n,m,s[114514],cnt,ans[114514],cnt1,flag;
void bld()
{
	for(int i=0;i<=m;i++)
		a[i].l=i-1,a[i].r=i+1,a[i].d=a[i].u=i;
	a[0].l=m,a[m].r=0;
	for(int i=1;i<=n;i++)
	{
		int begin=cnt,end=cnt;
		for(int j=1;j<=m;j++)
		{
			int x;
			scanf("%lld",&x);
			if(!x)
				continue;
			a[cnt].x=i,a[cnt].y=j;
			s[j]++;
			
			a[a[j].u].d=cnt;
			a[cnt].u=a[j].u;
			a[cnt].d=j;
			a[j].u=cnt;
			
			a[cnt].l=end;
			a[cnt].r=begin;
			a[end].r=cnt;
			a[begin].l=cnt;
			end=cnt;
			
			cnt++;
		}
	}
}
void del(int x)
{
	a[a[x].l].r=a[x].r;
	a[a[x].r].l=a[x].l;
	for(int i=a[x].d;i!=x;i=a[i].d)
		for(int j=a[i].l;j!=i;j=a[j].l)
		{
			a[a[j].u].d=a[j].d;
			a[a[j].d].u=a[j].u;
			s[a[i].y]--;
		}
}
void remove(int x)
{
	a[a[x].l].r=a[a[x].r].l=x;
	for(int i=a[x].d;i!=x;i=a[i].d)
		for(int j=a[i].l;j!=i;j=a[j].l)
		{
			a[a[j].u].d=a[a[j].d].u=j;
			s[a[i].y]++;
		}
}
void dfs()
{
	if(flag)
		return;
	if(a[0].r==0)
	{
		flag=1;
		for(int i=1;i<=cnt1;i++)
			printf("%lld ",ans[i]);
		return;
	}
	int minn=1e9,p=-1;
	for(int i=a[0].r;i;i=a[i].r)
	{
		if(!s[i])
			return;
		if(s[i]<minn)
		{
			minn=s[i];
			p=i;
		}
	}
	del(p);
	for(int i=a[p].d;i!=p;i=a[i].d)
	{
		ans[++cnt1]=a[i].x;
		for(int j=a[i].r;i!=j;j=a[j].r)
			del(a[j].y);
		dfs();
		
		--cnt1;
		for(int j=a[i].r;i!=j;j=a[j].r)
			remove(a[j].y);
	}
	remove(p);
}

signed main()
{
	cin>>n>>m;
	cnt=m+1;
	bld();
	dfs();
	if(!flag)
		cout<<"No Solution!";
}
2023/5/27 17:26
加载中...