[ACM] HUST 1017 Exact cover (Dancing Links,DLX模板題）

6 7
3 1 4 7
2 1 4
3 4 5 7
3 3 5 6
4 2 3 6 7
2 2 7

3 2 4 6

題目地址：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 
#include 
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]