Posted on 2011-04-12 22:27
Mato_No1 阅读(698)
评论(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引出的数独系列问题，精确覆盖可以直接秒杀。