随笔-72  评论-126  文章-0  trackbacks-0
整了一天的跳舞链,资料可以在网上搜到
http://sqybi.com/works/dlxcn/
惊讶于它做深搜的时候可以达到如此强劲的剪枝
下午的时候不看网上的模板自己写了一个,自认为是比模板少了一个for循环,但是写好后才发现没有模板的启发式搜索的效率,就这样活生生的TLE了,浪费了我好几个小时啊~~%>_<%~~
晚上只好写用模板的方法,写了一个后瞬间过了,感觉难度也不过尔尔
但这个舞蹈链可是容易解答却很难看出的主,构造舞蹈链还是关键
献上我的模板~~
最简单的舞蹈链,效率仅比hhanger差,可以跑240MS,不过后来我测出了一些数据的结构,暴力优化到了124MS,哈哈哈(得意一下)~~~
http://acm.hust.edu.cn/thanks/problem.php?id=1017
(精确覆盖问题)
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]) {
            
++S[Col[j]];
            U[D[j]] 
= j;
            D[U[j]] 
= j;
        }
    }
    L[R[c]] 
= c;
    R[L[c]] 
= c;
}
bool dfs() {
    
if(R[0== 0) {
        return true;
    }
    
int i , j;
    
int idx,minnum = 999999;
    
for(i = R[0];i != 0 ; i = R[i]) {
        
if(S[i] < minnum) {
            minnum 
= S[i];
            idx 
= i;
        }
    }
    remove(idx);
    
for(i = D[idx]; i != idx; i = D[i]) {
        ans[deep
++= Row[i];
        
for(j = R[i]; j != i ; j = R[j]) {
            remove(Col[j]);
        }
        
if(dfs()) {
            
return true;
        }
        deep 
--;
        
for(j = L[i]; j != i ; j = L[j]) {
            resume(Col[j]);
        }
    }
    resume(idx);
    
return false;
}
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3209
(精确覆盖问题)
浙大的这道省赛题其实就是完美覆盖的转化~把每一格都分开来,要求就是选N个方块把图完美覆盖全部搜完然后最小的个数
思路:行方块,列单位小格子,矩阵中1是方块所能覆盖的小格子

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507
(重复覆盖问题) 重复覆盖的模板题
献上模板
void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}
int h() {
    bool hash[51];
    memset(hash,false,sizeof(hash));
    int ret = 0;
    for(int c = R[0]; c != 0 ; c = R[c]) {
        if(!hash[c]) {
            ret ++;
            hash[c] = true;
            for(int i = D[c] ; i != c ; i = D[i]) {
                for(int j = R[i] ; j != i ; j = R[j]) {
                    hash[Col[j]] = true;
                }
            }
        }
    }
    return ret;
}
bool dfs(int deep,int lim) {
    if(deep + h() > lim) {
        return false;
    }
    if(R[0] == 0) {
        return true;
    }
    int idx , i , j , minnum = 99999;
    for(i = R[0] ; i != 0 ; i = R[i]) {
        if(S[i] < minnum) {
            minnum = S[i];
            idx = i;
        }
    }
    for(i = D[idx]; i != idx; i = D[i]) {
        remove(i);
        for(j = R[i]; j != i ; j = R[j]) {
            remove(j);
        }
        if(dfs(deep+1,lim)) {
            return true;
        }
        for(j = L[i]; j != i ; j = L[j]) {
            resume(j);
        }
        resume(i);
    }
    return false;
}

http://acm.tju.edu.cn/acm/showp3219.html
http://acm.hdu.edu.cn/showproblem.php?pid=2295
(重复覆盖问题)
这题无法转化成完美覆盖,所以remove和resume的时候要变化一下,但是这样还是会超时我看了标程才算AC。唉。。
主要是里边的一个A*的h函数是在是太犀利了,一下从TLE到了46MS。。。。剪枝还是非常重要的
思路:行是雷达,列是城市,矩阵中1是雷达覆盖城市

http://acm.fzu.edu.cn/problem.php?pid=1686
(重复覆盖问题)
这道题也同上道一样是:"在0-1矩阵中选取最少的行,使得每一列最少有一个1" 这个模型
所以和上一道建表一样建好之后套上模板就AC了~
思路:行是枚举在每个位子放魔法,列式怪物个数(最好给怪物标记个id),矩阵中的1是在这个地方放魔法是否能达到目标怪物

http://www.spoj.pl/problems/NQUEEN/
(重复覆盖问题)
N皇后问题,打的时候没能想到怎么转化成精确覆盖,只是用了dancing links的思想,傻傻的花了一个晚上完成了一个超级复杂的米字型链表(重复覆盖),开始的时候启发式函数S没有更新,导致没有发挥效用,结果本例30个0的数据都跑不出来,还以为是想法出错了,睡觉前在床上想到,改了一下,效率呈指数级增长,50个0的瞬间跑出来,在state里排到第一,哈哈

(精确覆盖问题)
今天CH教我怎么将之转化成十字链表的精确覆盖,但是矩阵是(n*n)*(6*n-2)比米字型链表n*n的大了好多倍,交了一下,跑了1s,效率不如米字型的
其思路是:行是格子数n*n,列是(行+列+正逆对角线),矩阵中的1是放在各自上所占得行,列,对角线
不需要全部搜完,只要初始皇后+dfs的深度达到n(放了n个皇后)就return true

http://acm.hdu.edu.cn/showproblem.php?pid=2828
(精确覆盖问题)
这题恶化N皇后一样可以转化成多种覆盖。我是精确覆盖,列是n+m只要精确前n个就够了
(重复覆盖问题)
还可以转化成不精确,那么列就是n

当然,此题出题人的意图是二分匹配。。。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=31
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
(重复覆盖问题)
这题要不和我说是dancing links 我还真看不出来
此题建表超烦,虽看出来但是建表就花了我一个半小时,还迫我使用上行的头节点,以前我只是用列的头节点,努力了很久,过了sample就AC了,烦就烦在建表上
思路:行是火柴棒数,列是完美时能构成的矩阵数目,矩阵中的1是列矩阵是否包含行火柴

http://acm.pku.edu.cn/JudgeOnline/problem?id=3074
http://acm.pku.edu.cn/JudgeOnline/problem?id=3076
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3038
(精确覆盖问题)
经典的数独,看了论文才明白怎么覆盖,9*9*9的行 (9+9+9)*9+9*9的列
思路:行是81个小格*每个格子的9个可能数字,列是81个小格+9行9列9小块的9个数字
每列确切的有4个1
开始读入的时候吧确定的数字的头上的1删掉可以很大的提高效率

http://acm.hdu.edu.cn/showproblem.php?pid=2518
超爽的dancing links
这题所有的方块可以旋转,这点超烦~
我差点就人肉代码了,枚举所有状态,不过最后我还是修改成不人肉的办法
只有几组答案,用dancing links暴力跑出所有组合后然后打表,嘿嘿,我就是这么猥琐的过的
72*所有摆放数~
思路:60个格子加12个方块作为列,所有摆放的方案数作为行


好了,A光上述题目dancing links的学习也告一段落,这个舞蹈是在是优美,以后出题一定要谱一曲经典的舞蹈~~



2009.9.6
发现dancing links还能做最大团
http://acm.hdu.edu.cn/showproblem.php?pid=1530
转化成补图后再建表。。。不过效率很低,跑了6000+MS,全部搜完找一个最大的,还没有更优的办法优化,尝试过二分再写个h函数未果。。。

10.15
http://acm.hdu.edu.cn/showproblem.php?pid=3156
和雷达类似,不过放radar的点要求出来,也是先二分枚举半径,然后利用两个点和半径确定一个圆心C(n,2),可以证明如果放其他地方一定没这个圆心优
posted on 2009-07-10 01:17 shǎ崽 阅读(11407) 评论(13)  编辑 收藏 引用

评论:
# re: 神奇的舞蹈~~Dancing_Links 2009-07-16 19:21 | majia
ZOJ 3184 是怎么做呢?是精确覆盖、重复覆盖还是直接使用dancing links思想?  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-07-30 09:49 | howie
我zoj-3209普通的dancing links要1040ms,
你的为什么那么快呢?请问做了什么优化?
  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-08-05 22:14 | 傻崽
@howie

其实关键在于建图的过称~~上边那个模板其实速度差别不是很大  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-08-17 22:06 | acmer
重复覆盖模板是不是有问题?没有对S[i]进行过其他操作,却每次遍历一遍?请指点  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-08-18 13:47 | 傻崽
@acmer


有的啊~初始的时候对S进行了赋值~这个S达到一个很强的剪枝的呢  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-09-07 21:44 | why
nuaa-1507-[解题]
我自己也模仿着写了个,但一直TLE
能否借你完整的代码学习学习呢~
这是我的邮箱:
weihaoo2@163.com
谢谢啊~
  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-09-08 21:29 | why
厄~不用了~A了~  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2009-12-25 23:40 | lccycc
膜拜大神!  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2011-03-05 19:22 | Snow_storm
大牛 请问构建链表的时候 是如何实现的呢?

我的dfs部分和大牛的几乎完全一样 但速度非常慢

求教  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2011-06-11 12:20 | 你m
敢把完整代码贴出来么
我C你M,浪费老子时间  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2011-07-29 16:13 | 你m你m
@你m
擦,这是博主年轻时候的作品,人可是玩了一年就进WF的,你算个球啊  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links 2011-08-06 09:12 | 刀刀
3 2
1 1 ON
2 1 ON 2 ON
1 2 ON

Hdu 2828 转化成精确覆盖的话,这一组数据会不会得-1,还是我理解错题意了?望大神解惑~  回复  更多评论
  
# re: 神奇的舞蹈~~Dancing_Links[未登录] 2013-09-23 10:56 | 柳晴
HDOJ:1530,用dancing links,lz能不能再讲详细点或者求代码?
  回复  更多评论
  

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