HUST 1017 Exact cover dance links

学习:请看 www.cnblogs.com/jh818012/p/3252154.html

模板题,上代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=;
const LL mod=1e9+;
int n,m,sz;
int u[N],l[N],r[N],d[N];
int col[N],row[N];
int h[],s[];
void init()
{
for(int i=;i<=m;++i)
{
s[i]=;
u[i]=d[i]=i;
l[i]=i-;
r[i]=i+;
}
r[m]=;l[]=m;
sz=m;
for(int i=;i<=n;++i)
h[i]=-;
}
void link(int x,int y)
{
++sz;
++s[y],col[sz]=y,row[sz]=x;
u[sz]=u[y],d[u[y]]=sz;
d[sz]=y,u[y]=sz;
if(h[x]==-)h[x]=l[sz]=r[sz]=sz;
{
l[sz]=l[h[x]];
r[l[h[x]]]=sz;
r[sz]=h[x];
l[h[x]]=sz;
}
}
void del(int y)
{
l[r[y]]=l[y];
r[l[y]]=r[y];
for(int i=d[y];i!=y;i=d[i])
{
for(int j=r[i];j!=i;j=r[j])
{
u[d[j]]=u[j];
d[u[j]]=d[j];
--s[col[j]];
}
}
}
void resume(int y)
{
for(int i=u[y];i!=y;i=u[i])
{
for(int j=l[i];j!=i;j=l[j])
{
d[u[j]]=u[d[j]]=j;
++s[col[j]];
}
}
r[l[y]]=l[r[y]]=y;
}
int ans[],tmp;
bool dance(int pos)
{
if(!r[])
{
tmp=pos;
return ;
}
int t=r[];
for(int i=r[];i!=;i=r[i])
if(s[i]<s[t])t=i;
del(t);
for(int i=d[t];i!=t;i=d[i])
{
ans[pos]=row[i];
for(int j=r[i];j!=i;j=r[j])
del(col[j]);
if(dance(pos+))return ;
for(int j=l[i];j!=i;j=l[j])
resume(col[j]);
}
resume(t);
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=;i<=n;++i)
{
int x,y;
scanf("%d",&x);
while(x--)
{
scanf("%d",&y);
link(i,y);
}
}
if(dance())
{
printf("%d",tmp);
for(int i=;i<tmp;++i)
printf(" %d",ans[i]);
printf("\n");
}
else printf("NO\n");
}
return ;
}
上一篇:Windows Store App JavaScript 开发:获取文件和文件夹列表


下一篇:[Effective Java]第九章 异常