舞蹈链,一个非常优雅的名字,实质上是搜索。
问题:给定一个n*m的矩阵,有些位置为1,有些位置为0。

  1. 选定最少的行,使得每列有且仅有一个1.(精确覆盖)
  2. 选定最少的行,使得每列至少一个1.(重复覆盖)
    实现是用了一个十字链表的数据结构,可以快速的删除和恢复矩阵的行列。

hiho1317

精确覆盖模板,要求选出一些行,使得每列恰好仅有一个棋子。

hiho1321, poj3074, zju3122

分析搬运Hihocoder
数独问题,精确覆盖。
对于精确覆盖问题的01矩阵,其实它的含义是这样:
列:一个原问题的约束条件
行:一个方案所满足的约束条件

  1. 每一个数字在每一行只能出现1次,由于行和数字的互相匹配,因此一共会产生9x9,81个约束条件;
  2. 每一个数字在每一列只能出现1次,由于列和数字的互相匹配,因此一共会产生9x9,81个约束条件;
  3. 每一个数字在每一个九宫只能出现1次,由于九宫和数字的互相匹配,因此一共会产生9x9,81个约束条件;
  4. 每一个格子只能填一个数字,由于一共有81个格子,所以也是81个约束条件;
    总共有324个约束条件,也就是说对于数独游戏来说,对应的01矩阵有324列。

数独问题的方案数为每一个格子可能填1-9这9个数字,一共有81个格子,所以总共是729个方案。
假设有方案在第i行第j列填写了数字k,其中第i行第j列是属于第t个九宫的格子。则其对应的约束条件为:
满足了第i行存在数字k。
满足了第j列存在数字k。
满足了第t个九宫存在数字k。
满足了第i行第j列填写有数字。
由此也可以看出,每一个方案恰好对应了4个约束条件。满足324个约束条件一共需要81个方案,也正好对应了数独游戏一共有81个格子的规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// LRJ写法
const int SLOT = 0;
const int ROW = 1;
const int COL = 2;
const int SUB = 3;
int encode(int i, int j, int k) {
return i * 256 + j * 16 + k + 1;
}
tuple<int, int, int> decode(int x) {
x--;
int i, j, k;
k = x % 16; x /= 16;
j = x % 16; x /= 16;
i = x % 16;
return make_tuple(i, j, k);
}
void build() {
for (int r = 0; r < 16; ++r)
for (int c = 0; c < 16; ++c)
for (int v = 0; v < 16; ++v) {
if (raw[r][c] == '-' || raw[r][c] == 'A' + v) {
vector<int> columns;
columns.push_back(encode(SLOT, r, c));
columns.push_back(encode(ROW, r, v));
columns.push_back(encode(COL, c, v));
columns.push_back(encode(SUB, (r/4)*4+c/4, v));
dlx.addRow(encode(r, c, v), columns);
}
}
}

hdu2295

$n$个城市,$m$个点可以放置雷达,要求不超过$k$雷达的情况下,把所有城市都覆盖每个雷达的半径至少是多少。
重复覆盖的模板题。
首先二分最终的答案$r$,矩阵的行是雷达,列是城市。
check是否存在一个方案使得在半径为$r$时,选最多$k$行能覆盖所有的列。

fzu1686

$nm$的01矩阵,每次操作可以将$n1m1$大小的一个小矩阵清零,问至少操作几次。
重复覆盖的模板题。

把所有为1的格点都标个号,列数就是为1的格点总数;
$n1m1$最小就是$11$的格子,那么在DLX中最多可选的行就有$n*m$行;
然后就建建边,跳个舞。

nowcoder119J

$n*m$的矩阵,有黑白两种颜色的格子,改变一个黑色可让自己和相邻四个方向的黑格子变白;
问最少需要改变几个黑格子,整个矩阵都是白格子;

和神龙那个题很像,有几个黑格子就几行,同样,有几个黑格子就几列;
然后把当前黑格子能影响到的黑格点建个边;
跳一下舞就好了。

zju3209

有一个大矩形,里面有一些小的矩形,用最少的矩形去覆盖这个大矩形,不允许重叠;
把大矩形看成$nm$个$11$的小矩形,然后就是一个精准覆盖的问题了;
有一个要注意的地方是建模的时候,矩形两条边重叠是不算的,比如这样两个[(0, 0), (15, 30)], [(15, 0), (30, 30)] (分别是左下角和右上角的坐标);