给一个矩阵 $N * M$ ,给你第 $i$ 行 $1$ 的个数和位置，让你选些行精确覆盖 $M$ 列(精确覆盖:每列有且只有 $1$ 个 $1$)。 例如：如下的矩阵:
11100001
10001110
10010110
00010010
00001100
就包含了这样一个集合(第 `1,4,5` 行)。
Input
多组数据，对于每组数据：
第一行两个整数 $N,M$ ；
接下来 $N$ 行，每行开头一个整数 $x$ ，表示该行上 $1$ 的个数，接下来 $x$ 个整数，每个 $1$ 的位置。
Output
如果有解随意输出组集合，否则输出 `NO` ，中间空格隔开。
提示：一个典型的跳舞链问题。跳舞链是一个比较古老的算法，这里梳理一下这道题的大致
思路：
- 如果当前矩阵只有一行：
- 如果全都是 ，说明已经找到了一种合法选法。
- 否则选法是不合法的，需要回溯。
- 枚举其中的一行，选择它。
- 删除掉矩阵中和被选择的这一行在相同列有 $1$ 的行。
- 删除掉被选择的这一行有 $1$ 的列。
- 递归向下继续操作。
- 如果没找到答案，把已删除的部分恢复。
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 10000000000
# define N 2005
# define M 2000005
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n, m;
int h[N], s[N], q[N];
int u[M], d[M], L[M], R[M], C[M], X[M];
void del(int c){ //delete ROW C
___(1)___;
___(2)___;
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[C[j]]--;
}
void add(int c) {
L[R[c]] = R[L[c]] = c;
for (int i = u[c]; i != c; i = u[i])
for (int j = L[i]; j != i; j = L[j])
u[d[j]] = d[u[j]] = j, s[C[j]]++;
}
void link(int r, int c) {
static int size = 0;
size++;
X[size] = r;
C[size] = c;
s[c]++;
d[size] = d[c];
u[size] = c;
u[d[size]] = size;
d[u[size]] = size;
if (h[r] == -1)
h[r] = L[size] = R[size] = size;
else {
R[size] = R[h[r]];
L[size] = h[r];
L[R[size]] = size;
R[L[size]] = size;
}
}
bool dance(int k) {
if (R[0] = 0) {
printf("%d", k);
for (int i = 1; i <= k; i++)
printf(" %d", X[q[i]]);
puts("");
return 1;
}
int mn = inf, c;
for (int i = R[0]; i; i = R[i])
if (s[i] < mn) mn = s[i], c = i;
___(3)___;
for (int i = d[c]; i != c; i = d[i]) {
q[k + 1] = i;
for (int j = R[i]; j != i; j = R[j]) ___(4)___;
if (dance(k + 1)) return 1;
for (int j = L[i]; j != i; j = L[j]) ___(5)___;
}
add(c);
return 0;
}
int main() {
while (scanf("%d%d", & n, & m) != EOF) {
for (int i = 0; i <= m; i++) {
d[i] = u[i] = i;
L[i + 1] = i;
R[i] = i + 1;
s[i] = 0;
}
R[m] = 0;
size = m;
int x, y;
for (int i = 1; i <= n; i++) {
h[i] = -1;
x = read();
while (x--) {
y = read();
link(i, y);
}
}
if (!dance(0)) puts("NO");
}
return 0;
}
1. A。
2. C。
3. C。
4. C。
5. A。
这段代码是经典的跳舞链，总的来说就是通过维护双向链表来动态解决行列的删除和恢复，每选择一行后就根据列上的 $1$ 将问题简化到更小数据规模的问题，以此来进行递归处理。更多的详细介绍的代码思路可以参考博客: https://www.cnblogs.com/grenet/p/3145800.html。