struct dl{
// x: line, y: column
struct node{
int c, left, right, up, down;
};
vector<node> a;
using vec = vector<int>;
using mat = vector<vec>;
vec cnt;
// 构造十字交叉循环链表有多种写法
// 1.流行的模板: link(int r, int c)，每次添加一个元素。另外需要个数组row[]，存储每一行中某个元素（可以是这一行中的任意元素，不必是最后一次添加的那个元素）的位置。
// 2.每次传入0-1矩阵中某一行的列编号数组
// 3.每次传入0-1矩阵的所有元素（我的实现即如此）
// 行列都从1开始编号，若不需要求答案则node中不用记录行编号
// m：0-1矩阵的列数
void build(const mat &b, int m){
a.clear();
cnt = vec(m+1);
for(int i=0; i<=m; i++)
a.push_back({i, (i+m)%(m+1), (i+1)%(m+1), i, i});
for(auto &i: b)
for(auto &j: i){
node cur={j, -1, -1, a[j].up, j};
a[cur.up].down=a.size();
a[cur.down].up=a.size();
if(j==i.front())
cur.left=cur.right=a.size();
else{
cur.left=a.size()-1;
cur.right=a.back().right;
a[cur.right].left=a.size();
a[cur.left].right=a.size();
}
a.push_back(cur);
++cnt[j];
}
}
// to cover some column
// no overhead!
void cover(int col){
// 删除第 col 列
a[a[col].right].left=a[col].left;
a[a[col].left].right=a[col].right;
// cnt[col]=0 // no need to do so.
// 删除所有在第 col 列有元素的行
for(int i=a[col].down; i!=col; i=a[i].down){
for(int j=a[i].right; j!=i; j=a[j].right){
a[a[j].up].down=a[j].down;
a[a[j].down].up=a[j].up;
// assert(a[j].y != col);
--cnt[a[j].c];
}
}
}
// to uncover some column
void uncover(int col){
// 恢复第 col 列
a[a[col].left].right=col;
a[a[col].right].left=col;
// 恢复所有在第 col 列有元素的行
for(int i=a[col].down; i!=col; i=a[i].down){
for(int j=a[i].right; j!=i; j=a[j].right){
a[a[j].up].down=j;
a[a[j].down].up=j;
++cnt[a[j].c];
}
}
}
void dance(int & res, int lev){
if(lev>=res) return; // 剪枝
int mi = INT_MAX, c=0;
for(int i=a[0].right; i; i=a[i].right)
if(cnt[i] < mi){
mi = cnt[i];
c = i;
}
if(c==0){
res=lev;
return;
};
// a[i].y == i holds.
cover(c);
// 枚举在第 i 列有元素的行
for(int i=a[c].down; i!=c; i=a[i].down){
// to choose some line
// res.push_back(a[i].x);
for(int j=a[i].right; j!=i; j=a[j].right){ // 覆盖在第 i 行有元素的列
cover(a[j].c);
}
// if(dance(res)) return true;
dance(res, lev+1);
// res.pop_back();
for(int j=a[i].left; j!=i; j=a[j].left){
uncover(a[j].c);
}
}
uncover(c);
return;
}
// constructor
};
Dancing Links 的原理可以参考 hihoCoder Week #101 和 Donold Knuth 的论文。
Dancing Links 的实现，网上的模板大都是 Knuth 论文里的伪代码风格： L[], R[], U[], D[], C[]四个数组。 构造双向十字循环链表的方法是定义 void link(int r, int c) 函数，每个插入一个元素（0-1矩阵中的某个1）。我认为这种写法是比较好的，简洁又灵活。我的实现与常见的写法略有不同，其差别无关紧要。
实现要点
- 若不要求输出具体方案，则无需存储每个元素的列。若需要输出具体方案，则往往涉及从0-1矩阵的行编号到对应的决策的解码（decode）操作。
- 选择0-1矩阵的某一行这一操作对应到对双向十字循环链表的操作中即“覆盖”（
cover()）这一行所能覆盖的那些列。 - 根据具体题目修改
dance()函数。