舞蹈链

说明

Dancing Links [Kuangbin带你飞] 模版及题解

这方面了解的非常不完善,有待添加

使用方法

Tips

模版

// 精确覆盖
const int MAXN = 1010;
const int MAXM = 1010;
const int MAXNODE = MAXN * MAXN;
struct DLX
{
    int n,m,sz;
    int U[MAXNODE],D[MAXNODE],R[MAXNODE],L[MAXNODE],Row[MAXNODE],Col[MAXNODE];
    int H[MAXN],S[MAXM];
    int ansd,ans[MAXN];

    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] = m;
        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 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])
                ++S[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    bool Dance(int d)
    {
        if(R[0] == 0)
        {
            ansd = d;
            printf("%d ",d);
            for (int i = 0 ; i < d ; i++)
                printf("%d%c",ans[i],i == d - 1 ? '\n' : ' ');  //输出选定的行
            return true;
        }
        int c = R[0];
        for(int i = R[0] ; i != 0 ; i = R[i])
            if(S[i] < S[c])
                c = i;
        Remove(c);
        for(int i = D[c] ; i != c ; i = D[i])
        {
            ans[d] = Row[i];
            for(int j = R[i] ; j != i ; j = R[j]) Remove(Col[j]);
            if(Dance(d + 1))return true;
            for(int j = L[i] ; j != i ; j = L[j]) resume(Col[j]);
        }
        resume(c);
        return false;
    }
};

results matching ""

    No results matching ""