昨天在刷PKU1084的時(shí)候，調(diào)了很久，發(fā)現(xiàn)原來(lái)那樣實(shí)現(xiàn)有缺陷。（原來(lái)的實(shí)現(xiàn)見(jiàn)
這里）
在重復(fù)覆蓋問(wèn)題中，刪去一整列的操作（delcol）是斷開(kāi)該列除了初始結(jié)點(diǎn)外的所有結(jié)點(diǎn)的左右鏈（delLR），這樣，如果有一些行預(yù)先已被選中，則刪去這一行（準(zhǔn)確來(lái)說(shuō)是對(duì)這一行所有結(jié)點(diǎn)執(zhí)行delcol操作），這時(shí)就會(huì)出現(xiàn)問(wèn)題，因?yàn)樵趧h去這一行的最后一個(gè)結(jié)點(diǎn)的時(shí)候，其左、右鏈都指向其本身，此時(shí)就無(wú)法刪掉這個(gè)結(jié)點(diǎn)。解決這一問(wèn)題的辦法是除了在矩陣中引入列頭以外，還要引入行頭（rowh），并且保證行頭不刪掉。這樣在刪掉一整行的時(shí)候就不會(huì)出問(wèn)題了。但是，如果這樣的話(huà)，需要在搜索過(guò)程中執(zhí)行delcol操作前進(jìn)行特判，保證不刪掉行頭結(jié)點(diǎn)（比如將行頭結(jié)點(diǎn)的U、D域置為-1），并且，在求啟發(fā)函數(shù)h()值的時(shí)候也要防止在行頭處出現(xiàn)問(wèn)題，可以將行頭結(jié)點(diǎn)的行列號(hào)均置為0。
而在精確覆蓋問(wèn)題中，刪去一整列的操作是斷開(kāi)結(jié)點(diǎn)的上下鏈而不是左右鏈，因此在刪去一整行時(shí)就不需要引入行頭結(jié)點(diǎn)。
下面是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;
}