Description
There is an N*M matrix with only 0s and 1s, (1 <= N,M <= 1000). An exact cover is a selection of rows such that every column has a 1 in exactly one of the selected rows. Try to find out the selected rows.
DLX精确覆盖的模板题。。。。。。
代码如下:
//HUST 1017 #include<iostream>
#include<cstring> using namespace std; // N 行 M 列 。 。 。 const int INF=10e8; const int MaxN=;
const int MaxM=;
const int MaxNode=MaxN*MaxM; // 这个的大小可以适当减少。 。 。 struct DLX
{
int U[MaxNode],D[MaxNode],L[MaxNode],R[MaxNode],col[MaxNode],row[MaxNode]; //row 可以不要。
int H[MaxN],S[MaxM];
int size,n,m;
int ansnum,ans[MaxN]; void init(int _n,int _m)
{
n=_n;
m=_m;
size=m;
ansnum=INF; for(int i=;i<=m;++i)
{
L[i]=i-;
R[i]=i+;
U[i]=D[i]=i; S[i]=;
}
R[m]=;
L[]=m; for(int i=;i<=n;++i)
H[i]=-;
} void Link(int r,int c)
{
col[++size]=c;
++S[c];
row[size]=r; U[size]=U[c];
D[size]=c;
D[U[c]]=size;
U[c]=size; if(H[r]==-)
H[r]=L[size]=R[size]=size;
else
{
L[size]=L[H[r]];
R[size]=H[r];
R[L[H[r]]]=size;
L[H[r]]=size;
}
} void remove(int c)
{
L[R[c]]=L[c];
R[L[c]]=R[c]; for(int i=D[c];i!=c;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 c)
{
for(int i=U[c];i!=c;i=U[i])
for(int j=L[i];j!=i;j=L[j])
{
U[D[j]]=D[U[j]]=j; ++S[col[j]];
} L[R[c]]=R[L[c]]=c;
} void showans(int d)
{
cout<<d; for(int i=;i<d;++i)
cout<<' '<<ans[i]; cout<<endl;
} bool Dance(int d)
{
if(R[]==)
{
showans(d); return ;
} int c=R[]; for(int i=R[];i;i=R[i])
if(S[i]<S[c])
c=i; remove(c); for(int i=D[c];i!=c;i=D[i])
{
ans[d]=row[i]; for(int j=R[i];j!=i;j=R[j])
remove(col[j]); if(Dance(d+))
return ; for(int j=L[i];j!=i;j=L[j])
resume(col[j]);
} resume(c); return ;
}
}; DLX dlx; int main()
{
ios::sync_with_stdio(false); int N,M,K;
int t; while(cin>>N>>M)
{
dlx.init(N,M); for(int i=;i<=N;++i)
{
cin>>K; for(int j=;j<=K;++j)
{
cin>>t; dlx.Link(i,t);
}
} if(!dlx.Dance())
cout<<"NO"<<endl;
} return ;
}