求助 TLE #7#9
查看原帖
求助 TLE #7#9
219869
Che_001楼主2021/7/27 11:29
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int Left[5010],Right[5010],up[5010],down[5010];
int sum[510],line[5010],col[5010]; 
int anscnt,ans[5010];
void init()
{
	for(int i=0;i<=m;i++)
	//Row 0 : special initialization;
	{
		Left[i]=i-1;
		Right[i]=i+1;
		up[i]=down[i]=i;
		sum[i]=0;
	}
	//head
	Left[0]=m;
	Right[m]=0;
	cnt=m+1;
}
void add_node(int &head,int &tail,int x,int y)
{
	line[cnt]=x,col[cnt]=y;
	sum[y]++;//cnt of this column;
	up[cnt]=up[y];
	down[up[y]]=cnt;
	up[y]=cnt;
	down[cnt]=y;
//	up[cnt]=y;
//	down[cnt]=down[y];
//	up[down[y]]=cnt;
//	down[y]=cnt;
	//在[y] and [up[y]] 中间插入[cnt] 
	Left[cnt]=tail;
	Right[cnt]=head;
//	Left[cnt]=head;
//	Right[cnt]=tail;
	Left[head]=Right[tail]=cnt;
	tail=cnt++;
}
void remove(int p)
{
	Left[Right[p]]=Left[p];
	Right[Left[p]]=Right[p];
	for(int i=down[p];i!=p;i=down[i])
	//类似于链式前向星
	{
		for(int j=Right[i];j!=i;j=Right[j])
		{
			//cout<<i<<" "<<j<<endl;
			sum[col[j]]--;
			up[down[j]]=up[j];
			down[up[j]]=down[j];
		} 
	}
}
void resum(int p)
{
	for(int i=up[p];i!=p;i=up[i])
	{
		for(int j=Left[i];j!=i;j=Left[j])
		{
			up[down[j]]=j,down[up[j]]=j;
			sum[col[j]]++;
		}
	}
	Left[Right[p]]=p;
	Right[Left[p]]=p;
}
bool dfs()
{
	if(Right[0]==0)
		return true;
	//为空 : return ok;
	int p=Right[0];
	for(int i=Right[0];i!=0;i=Right[i])
		if(sum[i]<sum[p])
			p=i;
	remove(p);
	for(int i=down[p];i!=p;i=down[i])
	{
		ans[++anscnt]=line[i];
		for(int j=Right[i];j!=i;j=Right[j])
			remove(col[j]);
		if(dfs()==true)
			return true;
		for(int j=Left[i];j!=i;j=Left[j])
			resum(col[j]);
		anscnt--;
	}
	resum(p);
	return false;
}
int main(int argc,const char *argv[])
{
	//ios::sync_with_stdio(false);
	//cin.tie(0),cout.tie(0);
	cin>>n>>m;
	init();
	for(int i=1;i<=n;i++)
	{
		int head=cnt,tail=cnt; 
		for(int j=1;j<=m;j++)
		{
			int var;
			cin>>var;
			if(var!=0)
				add_node(head,tail,i,j);
		}
	}
	if(dfs()==true)
	{
		for(int i=1;i<=anscnt;i++)
			cout<<ans[i]<<" ";
	}
	else
		cout<<"No Solution!";
	return 0;
}

2021/7/27 11:29
加载中...