现在的位置: 首页 > 综合 > 正文

DLX模板+练习

2018年02月21日 ⁄ 综合 ⁄ 共 1996字 ⁄ 字号 评论关闭

昨天和前天学习了DLX,在解决一类搜索问题(精确覆盖和重复覆盖)时具有很好的效果。

精确覆盖的定义:给定一个01矩阵,要求从中选出一些行,使得每列有且只有有一个一;

重复覆盖的定义:给定一个01矩阵,要求从中选出一些列,使得每列至少有一个一。

模板:(参考rabbit的模板

struct DLX {
    int L[maxn],R[maxn],U[maxn],D[maxn];
    int row[maxn],col[maxn];
    int ans[maxm],S[maxm],H[maxm];
    bool vis[maxn];
    int cnt,size;
    /*common part */
    void ini(int m) {
        for(int i=0; i<=m; i++) {
            S[i]=0;
            L[i]=i-1;
            R[i]=i+1;
            U[i]=D[i]=i;
        }
        memset(H,-1,sizeof(H));
        R[m]=0;
        L[0]=m;
        size=m+1;
    }
    void add(int x,int y) {
        //  cout<<x<<' '<<y<<endl;
        S[col[size]=y]++;
        row[size]=x;
        D[size]=D[y];
        U[D[y]]=size;
        U[size]=y;
        D[y]=size;
        if(H[x]<0) {
            H[x]=L[size]=R[size]=size;
        } else {
            R[size]=R[H[x]];
            L[R[H[x]]]=size;
            L[size]=H[x];
            R[H[x]]=size;
        }

        size++;
    }

    /*exact cover*/
    void Remove(int c) {
        L[R[c]]=L[c],R[L[c]]=R[c];
        for(int i=D[c]; i!=c; i=D[i])for(int j=R[i]; j!=i; j=R[j])
                U[D[j]]=U[j],D[U[j]]=D[j],S[col[j]]--;
    }
    void Resume(int c) {
        L[R[c]]=R[L[c]]=c;
        for(int i=U[c]; i!=c; i=U[i])for(int j=L[i]; j!=i; j=L[j])
                ++S[col[D[U[j]]=U[D[j]]=j]];
    }
    bool dance(int k) {
        int c;
        if((c=R[0])==0)return true;
        int tmp=inf;
        for(int i=R[0]; i; i=R[i])if(S[i]<tmp)tmp=S[i],c=i;
        Remove(c);
        for(int i=D[c]; i!=c; i=D[i]) {
            for(int j=R[i]; j!=i; j=R[j])Remove(col[j]);
            if(dance(k+1))return true;
            for(int j=L[i]; j!=i; j=L[j])Resume(col[j]);
        }
        Resume(c);
        return false;
    }
    /*repeat cover*/
    void Remove2(int c) {
        for(int i=D[c]; i!=c; i=D[i])
            L[R[i]]=L[i],R[L[i]]=R[i];
    }
    void Resume2(int c) {
        for(int i=U[c]; i!=c; i=U[i])
            L[R[i]]=R[L[i]]=i;
    }

    int Astar() {
        int res=0;
        for(int i=R[0]; i; i=R[i])vis[i]=false;
        for(int i=R[0]; i; i=R[i])if(!vis[i]) {
                res++,vis[i]=1;
                for(int j=D[i]; j!=i; j=D[j])
                    for(int k=R[j]; k!=j; k=R[k])
                        vis[col[k]]=1;
            }
        return res;
    }
    void dance2(int k,int &lim) {
        if(k+Astar()>=lim)return;
        if(R[0]==0) {
            if(lim>k)lim=k;
            return;
        }
        int c,tmp=inf;
        for(int i=R[0]; i!=0; i=R[i])
            if(S[i]<tmp)tmp=S[i],c=i;
        for(int i=D[c]; i!=c; i=D[i]) {
            Remove2(i);
            for(int j=R[i]; j!=i; j=R[j])Remove2(j);
            dance2(k+1,lim);
            for(int j=L[i]; j!=i; j=L[j])Resume2(j);
            Resume2(i);
        }
    }
} dlx;

一些题目:

精确覆盖模板题:

POJ 3740 Easy Finding

HUST 1017 Exact Cover 

ZOJ 3209 Treasure Map

精确覆盖 建图+输出方案:

HDU 3663 Power Stations


重复覆盖模板题:

HDU 2119 Matrix


重复覆盖+建图+输出方案:

HDU 2828 Lamp

FZU 1686 神龙的难题

重复覆盖+二分:

HDU 2295 Radar (二分距离)

HDU 3656 Fire Station  (二分距离坐标);


抱歉!评论已关闭.