随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

hust 1017 Exact Cover (Dancing Links)

/*
从昨天下午就开始搞,今天中午才搞定,Dancing Links 果然高深
神奇的双向环形十字链表······转的头晕了-_-||不过蛮有成就感的^v^
记录一下解题过程,先反反复复看了一遍Donald E.Knuth的论文,就开始攻hust 1017这道题目,
题目意思很明确:
给定一个由0和1组成的矩阵,是否能找到一个行的集合,使得集合中每一列都恰好包含一个1。

论文中有详细解答,具体思路就是:
1. 任意选择一列c,然后删除它(这个删除并不是普通的把这一列删除,而是要将这一列中有1的格子所在的行全部删除)
2. 然后对这一列上有1的每一行进行枚举,当枚举到第i行时
   该行上所有有1的列j全部删除(同上删除法)
3. 然后递归进入下一次,直到所有的列均被删除则有解
4. 恢复对j的删除
5. 恢复对c的删除
*/


#include 
<iostream>

using namespace std;

struct point {
    
int L;
    
int R;
    
int U;
    
int D;
    
int Sum;
    
int x, y;
}
p[ 1010 * 1010 ];

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列中每个有1的行
    i = c;
    
for(i = p[i].D; i != c; i = p[i].D) {
        j 
= i;
        p[ p[i].y ].Sum 
--;
        
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;
    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;
        }

    }

}


int dfs(int k) {
    
int i, j, l, m;

    
if(flag) return 1;

    
//得解输出
    if(p[ 0 ].R == 0{
        printf(
"%d", top);
        
for(i = 0; i < top; i++)
            printf(
" %d", stack[i]);
        puts(
"");
        flag 
= 1;
        
return 1;
    }


    
int c = 0;          //每次取出没有被覆盖的并且1的个数最小的一列
    int Min = INT_MAX;
    i 
= c;

    
for(i = p[i].R; i ; i = p[i].R) {
        
if(p[ p[i].y ].Sum < Min) {
            Min 
= p[ p[i].y ].Sum;
            c 
= i;
        }

    }



    
//将这一列删除
    CoverCol(c);
    i 
= c;
    
//枚举c列中的每一行
    for(i = p[i].D; i != c; i = p[i].D) {
        
//p[i].x 作为当前枚举的行,进栈
        stack[ top++ ] = p[i].x;
        j 
= i;

        
//对于该枚举的行,删除该行上1的格子所在的列
        for(j = p[j].R; j != i; j = p[j].R) {
            CoverCol(p[j].y);
        }

        
if ( dfs(k+1) )
            
return 1;

        
//对于该枚举的行,恢复该行上1的格子所在的列
        j = i;
        
for(j = p[j].L; j != i; j = p[j].L) {
            Release(p[j].y);
        }

        top 
--;
    }

    
//恢复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);
            
for(j = 0; j < k; j++{
                scanf(
"%d"&sor[j]);
                map[i][sor[j]] 
= T;
            }


            
int lef = Num(i, sor[0]);
            
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]);
                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;

        }


        p[
0].R = 1;

        
for(i = 1; i <= m; i++{
            
int No = Num(0, i);
            
            
if(i + 1 <= m)
                p[ No ].R 
= Num(0, i+1);
            
else
                p[ No ].R 
= 0;

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

            
int last = No;

            
for(j = 1; j <= n; j++{
                
if( map[j][i] == T ) {
                    p[ last ].Sum 
++;
                    
int now = Num(j, i);

                    p[ No ].D 
= now;
                    p[ now ].U 
= No;
                    
                    No 
= now;
                }

            }

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

            
if!p[ last ].Sum ) {
                printf(
"NO\n");
                
break;
            }

        }


        
if(i == m + 1{
            flag 
= 0;
            top 
= 0;
            dfs(
0);
            
if(!flag)
                puts(
"NO");
        }

    }

}

posted on 2009-04-04 12:14 英雄哪里出来 阅读(2170) 评论(3)  编辑 收藏 引用 所属分类: ACM

评论

# re: hust 1017 Exact Cover (Dancing Links)  回复  更多评论   

你这个dancing links 好阴险 .... 我怎么觉得这个很特殊呢?
希望大牛给点好的dancing links 的资料
fanxicai2000@163.com
2009-06-03 19:28 | doxi

# re: hust 1017 Exact Cover (Dancing Links)  回复  更多评论   

希望楼主多发点关于文关于dancing links
2009-09-17 10:31 | ScyNa

# re: hust 1017 Exact Cover (Dancing Links)  回复  更多评论   

表示不理解为什么通过这样的删减能确定是否有解呢?为什么可以这样做?好奇怪啊。。。
2011-10-18 01:00 | 海维

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理