dancing links精确覆盖模版

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int N=1000009,INF=0xffffff;
int n,m;///构造n行m列
int U[N],D[N],L[N],R[N];
int row[N],col[N];
int S[N],H[N],ans[N];

/**
int mas[4444][4444];
void print()
{
    memset(mas,0,sizeof(mas));
    for(int i=m+1;i<siz;i++)
    {
        mas[row[i]][col[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(i%num==0) cout<<endl;
        cout<<i%num<<": \t";
        for(int j=1;j<=m;j++)
        {
            cout<<mas[i][j];
            if(j%d==a) cout<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
**/
void init()
{
    for(int i=0;i<=m;i++)
    {
        L[i]=i-1;
        R[i]=i+1;
        col[i]=i;
        U[i]=D[i]=i;
        row[i]=-1;
    }
    R[m]=0;
    L[0]=m;
    siz=m+1;
    memset(H,0,sizeof(H));
    memset(S,0,sizeof(S));
    S[0]=INF+1;
}

void insert(int r,int c)
{
    U[siz]=U[c];
    D[siz]=c;
    U[D[siz]]=siz;
    D[U[siz]]=siz;
    if(H[r])
    {
        L[siz]=L[H[r]];
        R[siz]=H[r];
        L[R[siz]]=siz;
        R[L[siz]]=siz;
    }
    else H[r]=L[siz]=R[siz]=siz;
    row[siz]=r;
    col[siz]=c;
    S[c]++;
    siz++;
}

void build()
{
    init();
    /****************/
}

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)
{
    for(int i=U[c];i!=c;i=U[i])
    {
        for(int j=L[i];j!=i;j=L[j])
        {
            D[U[j]]=j;
            U[D[j]]=j;
            S[col[j]]++;
        }
    }
    R[L[c]]=c;
    L[R[c]]=c;
}

bool dfs(int k)
{
    if(R[0]==0) return true;
    int mins=INF,c=0;
    for(int t=R[0];t!=0;t=R[t])
    {
        if(S[t]<mins)
        {
            mins=S[t];
            c=t;
        }
    }
    if(c==0) return false;
    remove(c);
    for(int i=D[c];i!=c;i=D[i])
    {
        ans[k]=row[i];
        for(int j=R[i];j!=i;j=R[j]) remove(col[j]);
        if(dfs(k+1)) return true;
        for(int j=L[i];j!=i;j=L[j]) resume(col[j]);
    }
    resume(c);
    return false;
}

int main()
{
    while(/********scanf()********/)
    {
        /**********************/
        build();
        ///print();
        if(!dfs(0))
        {
            /**************No solution************/
        }
        /**********printf()*************/
    }
    return 0;
}

dancing links精确覆盖模版,布布扣,bubuko.com

dancing links精确覆盖模版

原文：http://blog.csdn.net/w750636248/article/details/21042909