RQNOJ P89,DLX重复覆盖……终于AC了

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理