Dancing Links解决Exact Cover问题.

用到了循环双向十字链表.

dfs.

论文一知半解地看了一遍,搜出一篇AC的源码,用注释的方法帮助理解.

HIT ACM

感谢源码po主.链接如下:

http://blog.csdn.net/yysdsyl/article/details/4266876

#include <iostream>

#include <cstdio>

using namespace std;

const int INT_MAX = 2147483647;

struct point {

    int L;

    int R;

    int U;

    int D;//四个方向的链表

    int Sum;

    int x, y;

}p[ 1010 * 1010 ];//这是直接开了一个point类型的数组,没有复用.1000*1000一维

//此处的链表并不是动态分配内存,而是一个静态的数组,只是他们提供的信息可以使得

//这个数组中的元素按照链表的功能运行

int n, m;

int i, j, k;

int map[1001][1001];

int sor[1001];

int flag;

int stack[1001], top;

int Num(int x, int y) {//将二维转化为一维

    return x * 1001 + y;

}

//删除c列

//所谓"删除",就是改变链表勾连搜索的关系!

void CoverCol(int c) {

    int i, j;

    p[ p[ c ].R ].L = p[ c ].L;

    p[ p[ c ].L ].R = p[ c ].R;

    //首先删除c列第0行

    //删除c列中每个有1的行

    i = c;

    for(i = p[i].D; i != c; i = p[i].D) {//结束条件:因为纵向也是循环的.这里体现了循环链表的方便之处

        j = i;//i是向下移动的

        p[ p[i].y ].Sum --;//其实就是p[c].Sum--;(把y看成R了..于是理解不能 = =b)

        for(j = p[j].R; j != i; j = p[j].R) {//由于是循环链表,一直往右走就能走到左边

            p[ p[j].D ].U = p[ j ].U;

            p[ p[j].U ].D = p[ j ].D;

        }

    }

}

//恢复c列

void Release(int c) {//恢复一列只需提供列数

    int i, j;

    p[ p[ c ].R ].L = c;//列数本身可寻址第0行

    p[ p[ c ].L ].R = c;

    //恢复c列中每个有1的行

    i = c;

    for(i = p[i].U; i != c; i = p[i].U) {//居然是循环上移...效果倒是没差

        j = i;

        p[ p[i].y ].Sum ++;

        for(j = p[j].L; j != i; j = p[j].L) {

            p[ p[j].D ].U = j;

            p[ p[j].U ].D = j;

        }

    }

}

//正常dfs都是递归

bool dfs(int k) {

    int i, j;

    if(flag) return 1;//dfs的返回值就是一个bool

    //得解输出,stack一路释放完~~~

    if(p[ 0 ].R == 0) {

        printf("%d", top);

        for(i = 0; i < top; i++)

            printf(" %d", stack[i]);

        puts("");//自带endl..

        flag = 1;

        return 1;

    }

    int c = 0;          //每次取出没有被覆盖的并且1的个数最小的一列,用于保存结果

    int Min = INT_MAX;//一种安全的初始化Min的方式

    //i = c;

    for(i = p[0].R; i ; i = p[i].R) {//i是列指针,遍历.***0.0的用处就是来初始化这里!所以它的左指针没用

        if(p[ p[i].y ].Sum < Min) {//第0行主要用来遍历列

            Min = p[ p[i].y ].Sum;

            c = i;

        }

    }

    //将这一列删除,同时删除这一列所有上有1的行

    CoverCol(c);

    i = c;

    //枚举c列中有1的的每一行,i向下移动

    for(i = p[i].D; i != c; i = p[i].D) {//仍然可看到循环

        //p[i].x 作为当前枚举的行，进栈

        stack[ top++ ] = p[i].x;//top指向栈顶元素之上位置,因为top表示数量,本就比下标多一

        j = i;

        /*****对于该枚举的行，删除该行上1的格子所在的列*****/

        //其实这种枚举就是一种标定,表示选择的路径(用了递归自身的特点,枚举即标定).

        //它实际上也存在

        /**"删除"只是脱离主体**///主体就是头指针指的那个

        //行本身还是连着的

        for(j = p[j].R; j != i; j = p[j].R) {

            CoverCol(p[j].y);

        }

        if ( dfs(k+1) )

            return 1;

        /**但是为什么要在这时递归??**/

        /**因为正常情况下,此时有可能到达终点,即是

        从本层调用开始,一个不空的矩阵,在一般情况下(不是仅限于n行1列的话),是会达到全空的.

        因此删到这里的时候进行下一次递归**/

        //这样看来,就是以枚举的点为交点(列其实是随机选择的,而行是枚举的,也就是说其实就是搜索

        //[终于看出来DLX是一种搜索了= =b]

        //只是状态的转移是根据十字链表而确定,我们所熟悉的是四方or六方move),将能够删除的全部删除,判断是否

        //已经到达终点,若是,成功;否则选择下一个(最小列+枚举行,其实就是从剩余状态中找出一种方案对其深搜的

        //策略之一)

        //还有,递归的特性:本层函数是k,那么里面包含k+1的调用,

        //查看k层函数运行到"调用k+1"之后又做了什么,可以看到和函数开头的呼应 

        //可以分两种情况分析清楚一个递归函数:

        //1.假设函数中的递归调用返回递归截止数据(参考基线情况),说明达到了怎样的终点

        //2.假设函数中的递归调用返回失败数据(有时有,有的递归没有),退回的路径是什么    

        //如果这样下去删不干净(下面的每一层都是return 0了)

        //对于该枚举的行，恢复该行上1的格子所在的列

        /**恢复,即是回溯**///设想一下,就像一个花卷~@

        j = i;

        for(j = p[j].L; j != i; j = p[j].L) {//循环左走

            Release(p[j].y);

        }

        top --;//枚举失败,pop掉.这种枚举每次都是不同的,不需要判重

    }

    //恢复c

    Release(c);

    return 0;

}

int main() {

    int T = 0;//每次循环特殊标记,不用每次清空

    while(scanf("%d %d", &n, &m) != EOF) {

        T ++;

        for(i = 1; i <= n; i++) {//一行一行进行处理

            scanf("%d", &k);//1的数目

            for(j = 0; j < k; j++) {

                scanf("%d", &sor[j]);//存原始数据的一个数组

                map[i][sor[j]] = T;//在map上还原图.用T标记!!

            }

            int lef = Num(i, sor[0]);//转化为一维后最左和最右1的下标

            int rig = Num(i, sor[k-1]);

//对数组的赋值过程其实就是链表的建立过程

            p[ lef ].L = rig;//循环起来,指针实际上是下标

            p[ lef ].x = i;

            p[ lef ].y = sor[0];//在图中的坐标

            for(j = 1; j < k; j++) {

                int cur = Num(i, sor[j]);//循环取出头节点之后的1's

                p[ Num(i, sor[j-1]) ].R = cur;//前一个节点的右指针接上

                p[ cur ].L = Num(i, sor[j-1]);//新节点的左指针接上

                p[ cur ].x = i;

                p[ cur ].y = sor[j];

            }

            p[ rig ].R = lef;//尾节点的右指针循环起来

        }

        //至此,整张图的每一行的循环双向链表建立完成~,Sum未赋值,默认为0

        p[0].R = 1;//图是从第1行开始的,这个第0行的右指针指向了1(也是第0行)???

//第0行有什么妙用??[后文有]

//0的左指针没有循环起来啊[后文有,注释在函数中]

        for(i = 1; i <= m; i++) {

            int No = Num(0, i);//其实就是i本身...

            if(i + 1 <= m)//caution!第一列也没有用!

                p[ No ].R = Num(0, i+1);

            else

                p[ No ].R = 0;//右指针循环起来

            //对第0行建立链表,0.0是循环点,不越界就全部连起来

            p[ No ].L = Num(0, i-1);

            p[ No ].x = 0;

            p[ No ].y = i;

            p[ No ].Sum = 0;//sum是干啥用的?[后文有]

            int last = No;//No就是当前的列指针

            for(j = 1; j <= n; j++) {//列一定时,搜索每一行

                if( map[j][i] == T ) {//如果此位有1

                    p[ last ].Sum ++;//第0行节点的sum成员存该行的1数目

                    int now = Num(j, i);//二维转一维

                    //开始构建十字链表~~

                    p[ No ].D = now;//纵向之前节点,挑有1的相连

                    p[ now ].U = No;//双向十字链表

                    No = now;//将last更新,that's why it is called 'last'!!!

                }

            }

            p[ No ].D = Num(0, i);

            p[ Num(0, i) ].U = No;//纵向循环起来

            if( !p[ last ].Sum ) {//若有一列全为0,不可能精确覆盖,直接退出

                printf("NO/n");

                break;

            }

        }

        if(i == m + 1) {//如果是正常退出(自然限制,不用标记变量,好!)

            flag = 0;

            top = 0;

            dfs(0);//DLX是深搜啊...

            if(!flag)

                puts("NO");

        }

        //不是正常退出说明已作出判断

    }

    return 0;

}

/**总结:DLX使用了基于静态数组的循环双向十字链表的"易恢复性",及其储存稀疏矩阵的简便性,

能较好地解决精确覆盖问题.**/