放了快2個(gè)月了……（準(zhǔn)確來說放了2年了，本沙茶從2年前就開始捉這道猥瑣題……）
DLX重復(fù)覆蓋的幾點(diǎn)說明：
（1）必須有啟發(fā)函數(shù)優(yōu)化，否則TLE；
（2）不需要二分下界，只要將目前f值（f=g+h，即實(shí)際深度加上啟發(fā)函數(shù)值）與目前求得的最優(yōu)解比較即可，f>=最優(yōu)解即剪枝；
（3）刪一整列（delcol）操作時(shí)，可以從任意一個(gè)結(jié)點(diǎn)開始刪（不一定要向精確覆蓋那樣非要從列頭開始），但是，開始的那個(gè)結(jié)點(diǎn)不刪！恢復(fù)（resucol）時(shí)也不恢復(fù)開始的那個(gè)結(jié)點(diǎn)！這是為了在接下來的橫向遍歷中不受影響。由于不刪開始結(jié)點(diǎn)，所以在將最優(yōu)列刪除時(shí)，需要循環(huán)一次刪除一次，恢復(fù)一次。
代碼：（RQNOJ P89）
#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 = 61, MAXM = 61, INF = ~0U >> 2;
struct DLnode {
int r, c, U, D, L, R;
} d[MAXN * MAXM];
int n, m, nodes, rowh[MAXN], cols[MAXM], res = INF;
void init_d()
{
re3(i, 0, m) {
d[i].r = 0; d[i].c = 0; 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;
memset(rowh, 0, n + 1 << 2); memset(cols, 0, m + 1 << 2); nodes = m + 1;
}
void add_node(int r, int 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];
if (rh) {
d[nodes].L = d[rh].L; d[nodes].R = rh; d[rh].L = nodes; d[d[nodes].L].R = nodes;
} else d[nodes].L = d[nodes].R = rowh[r] = nodes;
cols[c]++; nodes++;
}
void init()
{
scanf("%d%d", &m, &n);
init_d();
int k, x;
re1(i, n) {
scanf("%d", &k);
re(j, k) {
scanf("%d", &x); add_node(i, x);
}
}
}
void delUD(int x)
{
d[d[x].U].D = d[x].D; d[d[x].D].U = d[x].U;
}
void resuUD(int x)
{
d[d[x].U].D = d[d[x].D].U = x;
}
void delLR(int x)
{
d[d[x].L].R = d[x].R; d[d[x].R].L = d[x].L;
}
void resuLR(int x)
{
d[d[x].L].R = d[d[x].R].L = x;
}
void delcol(int c)
{
for (int i=d[c].D; i != c; i = d[i].D) delLR(i);
}
void resucol(int c)
{
for (int i=d[c].U; i != c; i = d[i].U) resuLR(i);
}
int h()
{
bool vst[MAXM]; memset(vst, 0, m + 1);
int z = 0;
for (int i=d[0].R; i; i = d[i].R) if (!vst[i]) {
vst[i] = 1; z++;
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 v)
{
if (v + h() >= res) return;
if (!d[0].R) {res = v; return;}
int min = INF, x;
for (int i=d[0].R; i; i = d[i].R) if (cols[i] < min) {min = cols[i]; x = i;}
for (int i=d[x].D; i != x; i = d[i].D) {
delcol(i);
for (int j=d[i].R; j != i; j = d[j].R) delcol(j);
dfs(v + 1);
for (int j=d[i].L; j != i; j = d[j].L) resucol(j);
resucol(i);
}
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
dfs(0);
pri();
return 0;
}
總結(jié)：DLX精確覆蓋和重復(fù)覆蓋其實(shí)是有大用的，很多搜索問題都可以轉(zhuǎn)化為這兩種問題，效率奇高無比，且寫起來也很容易（只是在建模的時(shí)候可能有點(diǎn)猥瑣，下面的模板，和網(wǎng)絡(luò)流一樣，10min的事），至于NOIP2009引出的數(shù)獨(dú)系列問題，精確覆蓋可以直接秒殺。