看了评测记录,别人代码感觉跑的速度是我的几倍。。
百思不得其解,求原因
#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;
}