DLX专题总结

const int N = 9;
const int maxn = N*N*N + 10;
const int maxnode=maxn*4+maxn+10;
const int INF=0x3f3f3f3f;

struct DLX{
    #define FF(i,A,S) for(int i = A[S];i != S;i = A[i])
    int L[maxnode],R[maxnode],U[maxnode],D[maxnode];//每个点的左右上下指针，所在行列
    int sz,col[maxnode],row[maxnode],S[maxn],H[maxn];//H每行的头结点,S每列的节点数
    int ans[maxn],cnt;
    int out[maxn];
    int n,m;

    void init(int _n,int _m) {
        n=_n, m=_m;
        for(int i = 0;i <= m;i ++)
            S[i]=0,U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;
        R[m] = 0, L[0] = sz = m;
        for(int i = 1;i <= n; ++i) H[i] = -1;
    }

    void link(int r,int c) {
        ++S[col[++sz]=c], row[sz] = r;
        D[sz] = D[c], U[D[c]] = sz;
        U[sz] = c, D[c] = sz;
        if(H[r] < 0) H[r] = L[sz] = R[sz] = sz;
        else R[sz]=R[H[r]], L[R[H[r]]]=sz,L[sz]= H[r],R[H[r]] = sz;
    }
    void del(int c){//精确覆盖,删除涉及C列的集合
        L[R[c]]=L[c],R[L[c]]=R[c];
        FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--S[col[j]];
    }
    void add(int c){  //精确覆盖,恢复涉及C列的集合
        R[L[c]]=L[R[c]]=c;
        FF(i,U,c)FF(j,L,i)++S[col[U[D[j]]=D[U[j]]=j]];
    }
    bool dance(int k){//精确覆盖
        //(剪枝)if(cnt != -1 && cnt <= d) return 0;//精确匹配输出最小
        if(!R[0]){
            //cnt=min(cnt,k);//精确匹配输出最小
            for(int i = 0;i < k; ++i)
                out[(ans[i]-1)/N]=(ans[i]-1)%N+1; //数独输出
            cnt=k;
            return 1;
        }
        int c=R[0];FF(i,R,0)if(S[c]>S[i])c=i;
        del(c);
        FF(i,D,c){
            FF(j,R,i)del(col[j]);
            ans[k]=row[i];
            if(dance(k+1))return 1;
            //dance(k+1);//精确匹配输出最小
            FF(j,L,i)add(col[j]);
        }
        add(c);
        return 0;
    }
    void remove(int c){//重复覆盖
        FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
    }
     void resume(int c){//重复覆盖
         FF(i,U,c)L[R[i]]=R[L[i]]=i;
    }
    int A(){//估价函数
        int res=0;
        bool vis[m+1];
        memset(vis,0,sizeof(vis));
        FF(i,R,0)if(!vis[i]){
                res++,vis[i]=1;
                FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
            }
        return res;
    }
    void dance(int now,int &ans){//重复覆盖,需要传入一个接收答案的ans
        if(R[0]==0)ans=min(ans,now);
        else if (now+A()>=limit) return ;
        else if(now+A()<ans){
            int temp=INF,c;
            FF(i,R,0)if(temp>S[i])temp=S[i],c=i;
            FF(i,D,c){
                remove(i);
                FF(j,R,i)remove(j);
                dance(now+1,ans);
                FF(j,L,i)resume(j);
                resume(i);
            }
        }
    }
}dlx;