[ACM] HUST 1017 Exact cover (Dancing Links,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.

INPUT

There are multiply test cases. First line: two integers N, M; The following N lines: Every line first comes an integer C(1 <= C <= 100), represents the number of 1s in this row, then comes C integers: the index of the columns whose value is 1 in this row.

OUTPUT

First output the number of rows in the selection, then output the index of the selected rows. If there are multiply selections, you should just output any of them. If there are no selection, just output "NO".

SAMPLE INPUT

SAMPLE OUTPUT

3 2 4 6

HINT

SOURCE

dupeng

题目地址：http://acm.hust.edu.cn/problem/show/1017

DLX 学习资料：

http://blog.sina.com.cn/s/blog_7d44748b01013fsf.html 图文并茂通过地址解释双向链表（基础！）

http://wenku.baidu.com/view/d8f13dc45fbfc77da269b126.html Knuth论文中文版

http://wenku.baidu.com/view/4ab7bd00a6c30c2259019eae.html Dancing Links在搜索中的应用 momodi论文

http://www.cnblogs.com/grenet/p/3145800.html 强烈推荐！作者把全然覆盖问题搜索过程完整得用文字和图片写了下来，非常好懂。

參考：http://www.cnblogs.com/kuangbin/p/3752854.html kuangbin模板

Dlx真的非常奇异，先是看资料，然后又研究模板，看完上面的链接资料对学习DLX非常有帮助。

最经典的就是全然覆盖问题。

本题就是给定一个由0，1元素组成的矩阵，问取出哪几行，能够使这几行构成的新矩阵，每列仅仅有一个1.

代码：

#include <iostream>
#include <stdio.h>
using namespace std;
const int maxnode=100010;
const int maxm=1010;
const int maxn=1010;

struct DLX
{
    int n,m,size;
    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
    int H[maxn];//行头节点
    int S[maxm];//每列有多少个节点
    int ansd,ans[maxn];//假设有答案，则选了ansd行，详细是哪几行放在ans[ ]数组里面，ans[0~ansd-1];

    void init(int _n,int _m)
    {
        n=_n,m=_m;
        for(int i=0;i<=m;i++)
        {
            S[i]=0;
            U[i]=D[i]=i;//初始状态下，上下自己指向自己
            L[i]=i-1;
            R[i]=i+1;
        }
        R[m]=0,L[0]=m;
        size=m;//编号，每列都有一个头节点，编号1-m
        for(int i=1;i<=n;i++)
            H[i]=-1;//每一行的头节点
    }

    void link(int r,int c)//第r行，第c列
    {
        ++S[Col[++size]=c];//第size个节点所在的列为c,当前列的节点数++
        Row[size]=r;//第size个节点行位置为r
        D[size]=D[c];//以下这四句头插法（图是倒着的？)
        U[D[c]]=size;
        U[size]=c;
        D[c]=size;
        if(H[r]<0)
            H[r]=L[size]=R[size]=size;
        else
        {
            R[size]=R[H[r]];
            L[R[H[r]]]=size;
            L[size]=H[r];
            R[H[r]]=size;
        }
    }

    void remove(int c)//删除节点c，以及c上下节点所在的行,每次调用这个函数，都是从列头节点開始向下删除，这里c也能够理解为第c列
    {                 //由于第c列的列头节点编号为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)//恢复节点c,以及c上下节点所在的行(同上，也能够理解为从第c列的头节点開始恢复
    {
        for(int i=U[c];i!=c;i=U[i])
            for(int j=L[i];j!=i;j=L[j])
            ++S[Col[U[D[j]]=D[U[j]]=j]]; //打这一行太纠结了 T T
        L[R[c]]=R[L[c]]=c;
    }

    bool dance(int d)//递归深度
    {
        if(R[0]==0)
        {
            ansd=d;
            return true;
        }
        int c=R[0];
        for(int i=R[0];i!=0;i=R[i])
            if(S[i]<S[c])
            c=i;
        remove(c);//找到节点数最少的列，当前元素不是原图上0，1的节点，而是列头节点
        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 true;
            for(int j=L[i];j!=i;j=L[j])
                resume(Col[j]);
        }
        resume(c);
        return false;
    }
};

DLX x;
int n,m;

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        x.init(n,m);
        for(int i=1;i<=n;i++)
        {
            int cnt,j;
            scanf("%d",&cnt);
            while(cnt--)
            {
                scanf("%d",&j);
                x.link(i,j);
            }
        }
        if(!x.dance(0))
            printf("NO
");
        else
        {
            printf("%d",x.ansd);
            for(int i=0;i<x.ansd;i++)
                printf(" %d",x.ans[i]);
            printf("
");
        }
    }
    return 0;
}