昨天在刷PKU1084的时候，调了很久，发现原来那样实现有缺陷。（原来的实现见
这里）
在重复覆盖问题中，删去一整列的操作（delcol）是断开该列除了初始结点外的所有结点的左右链（delLR），这样，如果有一些行预先已被选中，则删去这一行（准确来说是对这一行所有结点执行delcol操作），这时就会出现问题，因为在删去这一行的最后一个结点的时候，其左、右链都指向其本身，此时就无法删掉这个结点。解决这一问题的办法是除了在矩阵中引入列头以外，还要引入行头（rowh），并且保证行头不删掉。这样在删掉一整行的时候就不会出问题了。但是，如果这样的话，需要在搜索过程中执行delcol操作前进行特判，保证不删掉行头结点（比如将行头结点的U、D域置为-1），并且，在求启发函数h()值的时候也要防止在行头处出现问题，可以将行头结点的行列号均置为0。
而在精确覆盖问题中，删去一整列的操作是断开结点的上下链而不是左右链，因此在删去一整行时就不需要引入行头结点。
下面是PKU1084的AC代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 60, MAXM = 55, INF = ~0U >> 2;
struct dlnode {
int r, c, U, D, L, R;
} d[(MAXN + 1) * (MAXM + 1)];
int _n, n, m, nodes, rowh[MAXN + 1], cols[MAXM + 1], B[5][5][4], res;
bool A[MAXN + 1], vst[MAXN];
void init_d()
{
re3(i, 0, m) {d[i].U = d[i].D = i; d[i].L = i - 1; d[i].R = i + 1;} d[0].L = m; d[m].R = 0;
nodes = m; re1(i, n) {rowh[i] = ++nodes; d[nodes].L = d[nodes].R = nodes; d[nodes].U = d[nodes].D = -1;}
re1(i, m) cols[i] = 0;
}
void add_node(int r, int c)
{
cols[c]++; d[++nodes].r = r; d[nodes].c = c;
d[nodes].U = d[c].U; d[nodes].D = c; d[c].U = nodes; d[d[nodes].U].D = nodes;
int rh = rowh[r]; d[nodes].L = d[rh].L; d[nodes].R = rh; d[rh].L = nodes; d[d[nodes].L].R = nodes;
}
void delLR(int x)
{
d[d[x].L].R = d[x].R; d[d[x].R].L = d[x].L;
}
void delUD(int x)
{
d[d[x].U].D = d[x].D; d[d[x].D].U = d[x].U;
}
void resuLR(int x)
{
d[d[x].L].R = d[d[x].R].L = x;
}
void resuUD(int x)
{
d[d[x].U].D = d[d[x].D].U = x;
}
void delcol(int x)
{
for (int i=d[x].D; i != x; i=d[i].D) delLR(i);
}
void resucol(int x)
{
for (int i=d[x].U; i != x; i=d[i].U) resuLR(i);
}
void prepare()
{
int x = 0;
re(i, _n) {
re(j, _n) {B[i][j][0] = ++x; B[i][j][1] = x + _n; B[i][j][2] = x + _n + 1; B[i][j][3] = x + _n + _n + 1;}
x += _n + 1;
}
x = 0;
re(i, _n) re(j, _n - i) re(k, _n - i) {
x++;
re(t, i+1) {
add_node(B[j][k + t][0], x);
add_node(B[j + t][k][1], x);
add_node(B[j + t][k + i][2], x);
add_node(B[j + i][k + t][3], x);
}
}
int rh;
re1(i, n) if (A[i]) {
rh = rowh[i];
for (int j=d[rh].R; j != rh; j=d[j].R) delcol(j);
}
res = n;
}
int h()
{
re1(i, m) vst[i] = 0;
int z = 0;
for (int i=d[0].R; i; i=d[i].R) if (!vst[i]) {z++; vst[i] = 1; for (int j=d[i].D; j != i; j=d[j].D) for (int k=d[j].R; k != j; k=d[k].R) vst[d[k].c] = 1;}
return z;
}
void dfs(int dep)
{
int h0 = h(); if (dep + h0 >= res) return; else if (!h0) {res = dep; return;}
int mins = INF, c0; for (int i=d[0].R; i; i=d[i].R) if (!cols[i]) return; else if (cols[i] < mins) {mins = cols[i]; c0 = i;}
for (int i=d[c0].D; i != c0; i=d[i].D) {
delcol(i); for (int j=d[i].R; j != i; j=d[j].R) if (d[j].U != -1) delcol(j);
dfs(dep + 1);
for (int j=d[i].L; j != i; j=d[j].L) if (d[j].U != -1) resucol(j); resucol(i);
}
}
int main()
{
int tests, _n0, x;
scanf("%d", &tests);
re(testno, tests) {
scanf("%d%d", &_n, &_n0);
n = _n * (_n + 1) << 1; m = 0; re1(i, _n) m += i * i; init_d(); re1(i, n) A[i] = 0;
re(i, _n0) {scanf("%d", &x); A[x] = 1;}
prepare();
dfs(0);
printf("%d\n", res);
}
return 0;
}