求助被卡常原因
查看原帖
求助被卡常原因
177069
李白莘莘学子楼主2020/6/18 21:43

看了评测记录,别人代码感觉跑的速度是我的几倍。。

百思不得其解,求原因

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define N 250507 
using namespace std; 
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n2,m2,cnt;
int r[N],l[N],u[N],d[N],row[N],col[N];
//每个点的左,右,上下,行,列信息
int h[N],s[N],ans,ansk[N];
void init(int m1)
{
	int m=m1;
	for(int i=0;i<=m;i++)
	{
		r[i]=i+1;
		l[i]=i-1;
		u[i]=d[i]=i;
	}//初始化C数组的十字链表信息。
	r[m]=0;
	l[0]=m;
	memset(h,-1,sizeof(h));
	cnt=m+1;
}
inline void link(int x,int y)
{
	s[x]++;
	row[cnt]=x;col[cnt]=y;
	u[cnt]=y;
	d[cnt]=d[y];
	u[d[y]]=cnt;
	d[y]=cnt;
	if(h[x]<0)h[x]=r[cnt]=l[cnt]=cnt;
	else
	{
		r[cnt]=h[x];//当前节点右链连接到最左端元素 
		l[cnt]=l[h[x]];//当前节点做链连接到上一个元素 
		r[l[h[x]]]=cnt;//更新上一个节点的右链 
		l[h[x]]=cnt;//更新最左端节点的左链 
	} 
	cnt++;
	return; 
}
inline void remove(int c)
{
	r[l[c]]=r[c];//更新左右链 
	l[r[c]]=l[c];
	for(re int i=d[c];i!=c;i=d[i])
	{
		for(re int j=r[i];j!=i;j=r[j])
		{
			u[d[j]]=u[j];
			d[u[j]]=d[j];
			s[col[j]]--;
		}
	}
}
inline void resume(int c)
{
	//Orz DL 
	for(re int i=u[c];i!=c;i=u[i])
	{
		for(re int j=l[i];j!=i;j=l[j])
		{
			u[d[j]]=j;
			d[u[j]]=j;
			s[col[j]]++;
		}
	}
	r[l[c]]=c;
	l[r[c]]=c;
}
bool dance(int deep)
{
	if(r[0]==0)
	{
		register int i=0;
		for(i=0;i<deep;i++)printf("%d ",ansk[i]);
    	return 1;
	}
	int c=r[0];
	for(re int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
	remove(c);
	for(re int i=d[c];i!=c;i=d[i])
	{
		ansk[deep]=row[i];
		for(re int j=r[i];j!=i;j=r[j])remove(col[j]);
		if(dance(deep+1)==1)return 1;
		for(re int j=l[i];j!=i;j=l[j])resume(col[j]);
	}
	resume(c); 
	return 0;
}
int main()
{
	n2=read(),m2=read();
	register int i,j;
	int f;
	init(m2);
	for(i=1;i<=n2;i++)
	{
		for(j=1;j<=m2;j++)
		{
			f=read();
			if(f)link(i,j);
		}
	}
	if(!dance(0))printf("No Solution!");
	return 0;
}

2020/6/18 21:43
加载中...