【POJ 3740】Easy Finding(DLX算法)

08
Sep

【POJ 3740】Easy Finding(DLX算法)

今天看数独问题的时候知道了DLX这种东西,查资料看了挺久才算看懂,然后写出来又花了不少时间,记录在这里。
首先推荐一篇讲解很好的文章 跳跃的舞者,舞蹈链(Dancing Links)算法——求解精确覆盖问题

题面描述
给定一个只有0和1的矩阵,要求从中挑出一些行组成新的矩阵,从而使新矩阵中每一列有且只有一个1
解题思路
精确覆盖模板题
采用双向十字循环链表实现数据存储,实际上DLX这东西巧妙和难点也就在这个数据结构上,搞懂了这个也就搞清楚所有东西了。
代码编写
搞懂了以后怎么写真的是个大问题。我纠结很久,最终通过细拆操作并且debug了挺久,搞定。详细请看我的代码,有完备的注释。另外这题而言,注意用cin/cout会TLE。

AC代码
https://paste.ubuntu.com/25489933/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论