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
       
        #include
        
         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<
         
          >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"<