精确覆盖DLX算法模板

时间：2022-07-18 17:13:00

代码

struct DLX

{

    int n,id;

    int L[maxn],R[maxn],U[maxn],D[maxn];

    int C[maxn],S[maxn],loc[maxn][];

    void init(int nn=) //传列长

    {

        n=nn;

        for(int i=;i<=n;i++) U[i]=D[i]=i,L[i]=i-,R[i]=i+;

        L[]=n; R[n]=;

        id=n;

        memset(S,,sizeof(S));

    }

    void AddRow(int x,int col,int A[]) //传入参数是行标号，列长，列数组

    {

        bool has=false;

        int first=id+;

        for(int y=;y<=col;y++)

        {

            if(A[y]==) continue;

            has=true;

            ++id;

            L[id]=id-; R[id]=id+;

            D[id]=y; U[id]=U[y];

            D[U[y]]=id; U[y]=id;

            loc[id][]=x,loc[id][]=y;

            C[id]=y; S[y]++;

        }

        if(!has) return;

        R[id]=first; L[first]=id;

    }

    void Remove(int Size)

    {

        for(int j=D[Size];j!=Size;j=D[j])//将左右两边连接

            L[R[j]]=L[j],R[L[j]]=R[j];

    }

    void Resume(int Size)

    {

        for(int j=U[Size];j!=Size;j=U[j])//恢复

            L[R[j]]=R[L[j]]=j;

    }

    bool vis[ms];//标记行是否访问过

    int h() //启发式函数

    {

        int ret=;

        int i,j,k;

        memset(vis,,sizeof(vis));

        for(i=R[];i;i=R[i])

        {

           if(vis[i]) continue;

           ret++;

           for(j=D[i];j!=i;j=D[j]) //所有关联的标记了

               for(k=R[j];k!=j;k=R[k]) vis[C[k]]=;

        }

        return ret;

    }

    void dfs(int step)

    {

        if(step+h()>=ans) return;

        if(R[]==){ ans=min(ans,step); return; }

        int Min=INF,c=-;

        for(int i=R[];i;i=R[i]) if(Min>S[i]){ Min=S[i]; c=i; }

        for(int i=D[c];i!=c;i=D[i])

        {

            Remove(i);

            for(int j=R[i];j!=i;j=R[j]) Remove(j);

            dfs(step+);

            for(int j=L[i];j!=i;j=L[j]) Resume(j);

            Resume(i);

        }

        return;

    }

}dlx;

相关文章