首页 > 代码库 > (简单) HUST 1017 Exact cover , DLX+精确覆盖。
(简单) HUST 1017 Exact cover , DLX+精确覆盖。
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=1010;const int MaxM=1010;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=0;i<=m;++i) { L[i]=i-1; R[i]=i+1; U[i]=D[i]=i; S[i]=0; } R[m]=0; L[0]=m; for(int i=1;i<=n;++i) H[i]=-1; } 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]==-1) 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=0;i<d;++i) cout<<‘ ‘<<ans[i]; cout<<endl; } bool Dance(int d) { if(R[0]==0) { showans(d); return 1; } int c=R[0]; for(int i=R[0];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+1)) return 1; for(int j=L[i];j!=i;j=L[j]) resume(col[j]); } resume(c); return 0; }};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=1;i<=N;++i) { cin>>K; for(int j=1;j<=K;++j) { cin>>t; dlx.Link(i,t); } } if(!dlx.Dance(0)) cout<<"NO"<<endl; } return 0;}
(简单) HUST 1017 Exact cover , DLX+精确覆盖。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。