DLX80pts TLEon#7#9求调
查看原帖
DLX80pts TLEon#7#9求调
648843
wdl_楼主2024/2/24 16:39
#include<bits/stdc++.h>
#define int long long
#define up(x,y,z) for(int (x) = (y);(x) <= (z);(x) ++)
#define down(x,y,z) for(int (x) = (y);(x) >= (z);(x) --)
using namespace std;
int n,m;
int a[5005][5005];
int l[5005],r[5005],u[5005],d[5005],row[5005],col[5005];
int tot[5005],fir[5005],cnt;
int ans[5005];
void init()
{
	up(i,0,m)
	{
		u[i] = d[i] = i;
		l[i] = i - 1;
		r[i] = i + 1;
	}
	r[m] = 0;
	l[0] = m;
	cnt = m;
}
void join(int R,int C)
{
	cnt ++;
	row[cnt] = R;
	col[cnt] = C;
	tot[C] ++;
	d[cnt] = C;
	u[cnt] = u[C];
	d[u[cnt]] = cnt;
	u[C] = cnt;
	if(!fir[R])fir[R] = l[cnt] = r[cnt] = cnt;
	else
	{
		r[cnt] = fir[R];
		l[cnt] = l[fir[R]];
		r[l[fir[R]]] = cnt;
		l[fir[R]] = cnt;
	}
}
void remove(int C)
{
	r[l[C]] = r[C];
	l[r[C]] = l[C];
	for(int i = u[C];i != C;i = u[i])
	{
		for(int j = l[i];j != i;j = l[j])
		{
			u[d[j]] = u[j];
			d[u[j]] = d[j];
			tot[col[j]] --;
		}
	}
}
void resume(int C)
{
	for(int i = u[C];i != C;i = u[i])
	{
		for(int j = l[i];j != i;j = l[j])
		{
			u[d[j]] = j;
			d[u[j]] = j;
			tot[col[j]] ++;
		}
	}
	r[l[C]] = C;
	l[r[C]] = C;
}
bool dance(int deep)
{
	if(r[0] == 0)
	{
		//cout << ans[0] << endl;
		up(i,1,deep - 1)
			cout << ans[i] << ' ';
		return 1;
	}
	int C = r[0];
	for(int i = r[0];i != 0;i = r[i])
	{
		if(tot[i] < tot[C])C = i;
	}
	remove(C);
	for(int i = u[C];i != C;i = u[i])
	{
		ans[deep] = row[i];
		for(int j = l[i];j != i;j = l[j])
		{
			remove(col[j]);
		}
		if(dance(deep + 1))return 1;
		for(int j = r[i];j != i;j = r[j])
		{
			resume(col[j]);
		}
	}
	resume(C);
	return 0;
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> m;
	init();
	up(i,1,n)
	{
		up(j,1,m)
		{
			cin >> a[i][j];
			if(a[i][j])join(i,j);
		}
	}
	if(!dance(1))
		cout << "No Solution!";
	return 0;
}

2024/2/24 16:39
加载中...