Posted on 2011-04-12 22:27
Mato_No1 閱讀(775)
評論(0) 編輯 收藏 引用 所屬分類:
搜索
放了快2個月了……（準確來說放了2年了，本沙茶從2年前就開始捉這道猥瑣題……）
DLX重復覆蓋的幾點說明：
（1）必須有啟發函數優化，否則TLE；
（2）不需要二分下界，只要將目前f值（f=g+h，即實際深度加上啟發函數值）與目前求得的最優解比較即可，f>=最優解即剪枝；
（3）刪一整列（delcol）操作時，可以從任意一個結點開始刪（不一定要向精確覆蓋那樣非要從列頭開始），但是，開始的那個結點不刪！恢復（resucol）時也不恢復開始的那個結點！這是為了在接下來的橫向遍歷中不受影響。由于不刪開始結點，所以在將最優列刪除時，需要循環一次刪除一次，恢復一次。
代碼：（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;
}
總結：DLX精確覆蓋和重復覆蓋其實是有大用的，很多搜索問題都可以轉化為這兩種問題，效率奇高無比，且寫起來也很容易（只是在建模的時候可能有點猥瑣，下面的模板，和網絡流一樣，10min的事），至于NOIP2009引出的數獨系列問題，精確覆蓋可以直接秒殺。