DLX学习笔记

2023-11-18 11:33:58

DLX

\(\text{DLX}\)，舞蹈链，主要解决精确覆盖问题和重复覆盖问题。

本文暂时只介绍精确覆盖问题。

重复覆盖问题不知什么时候再更。

1. 模板题

P4929 【模板】舞蹈链（DLX）

题意：

给定一个 \(N\) 行 \(M\) 列的矩阵，矩阵中每个元素要么是1，要么是0

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 \(j\) ，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。

大致思路

大致将这一类问题总结成了几个步骤。

建模，将问题转换成如上题的模板。
开始写板子。

而板子大致又分成如下几个步骤：

将用十字链表的图建出来。
选中一行，将其中有一的每一列标记出来。
再将标记出的每一列中有一的那一行标记出来。
将所有标记的删掉，合成新矩阵。
若新矩阵不为空，则重复上述步骤；若为空，判断之前是否全为一，若是，则有解，否则无解。

现在应该比较清晰了吧。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 6000;

int n , m , tot , cnt;
int l[maxn] , r[maxn] , d[maxn] , u[maxn];
int qx[maxn] , qy[maxn] , vy[maxn] , ans[maxn];

inline int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

inline void init()
{
    for(int i = 0;i <= m;i++)
    {
        l[i] = i - 1 , r[i] = i + 1;
        u[i] = d[i] = i;
    }
    r[m] = 0 , l[0] = m;
    cnt = m + 1;
}

inline void add(int &ll , int &rr , int x , int y)
{
    qx[cnt] = x , qy[cnt] = y , vy[y]++;
    u[cnt] = y , d[cnt] = d[y] , u[d[y]] = cnt , d[y] = cnt;
    r[ll] = l[rr] = cnt , l[cnt] = ll , r[cnt] = rr;
    rr = cnt++; 
}

inline void remove(int p)
{
    l[r[p]] = l[p] , r[l[p]] = r[p];
    for(int i = d[p];i != p;i = d[i])
        for(int j = l[i];j != i;j = l[j])
        {
            vy[qy[j]]--;
            u[d[j]] = u[j] , d[u[j]] = d[j];
        }
    return;
}

inline void resume(int p)
{
    for(int i = u[p];i != p;i = u[i])
        for(int j = r[i];j != i;j = r[j])
        {
            vy[qy[j]]++;
            u[d[j]] = d[u[j]] = j;
        }
    l[r[p]] = r[l[p]] = p;
    return;
}

inline bool dfs()
{
    if(!r[0]) return true;
    int p = r[0];
    for(int i = r[0];i;i = r[i])
        if(vy[p] > vy[i]) p = i;
    remove(p);
    for(int i = d[p];i != p;i = d[i])
    {
        ans[++tot] = qx[i];
        for(int j = r[i];j != i;j = r[j]) remove(qy[j]);
        if(dfs()) return true;
        for(int j = l[i];j != i;j = l[j]) resume(qy[j]);
        tot--;
    }
    resume(p);
    return false;
}

int main()
{
    n = read() , m = read();
    init();
    for(int i = 1;i <= n;i++)
    {
        int ll = cnt , rr = cnt;
        for(int j = 1;j <= m;j++)
        {
            int x = read();
            if(x) add(ll , rr , i , j);
        }
    }
    if(dfs())
        for(int i = 1;i <= tot;i++) cout << ans[i] << " ";
    else
        cout << "No Solution!";
    return 0;
}

2.数独

生为一个懒人，这就是最后一题了。

SP13980 SUDOGOB - Sudoku goblin

一道显然的 \(\text{DLX}\) 模板题。

这里注重讲一下如何建模。

建模

首先考虑一个数独，需要满足的条件。

每一行都需要不同。
每一列都需要不同。
每一个宫格都需要不同。
八十一个格子都不能为 \(0\) 。

注意最后一个情况，这是最容易遗漏的一个情况。

根据 \(\text{DLX}\) 性质，我们不妨将每一种情况设为每一行，而每一个限制设为每一列，就建出了模型。

考虑每一种情况

我们让 \(a_{i,j}\) 为第 \(i\) 行，第 \(j\) 列上的数。

当 \(a_{i,j}\) 为 \(0\) 时。

那么这个位置九个数都有可能被填，那么就都需要加上去。

当 \(a_{i,j}\) 不为 \(0\) 时。

那么这个位置就只有唯一的解法。

考虑每一种限制

对于之前的情况，我们需要在不同的列中，根据限制加点。

由于有四个限制，我们可以加四个点。

代码大致如下：

add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 0 + (i - 1) * 9 + j);
add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 1 + (i - 1) * 9 + k);
add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 2 + (j - 1) * 9 + k);
add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 3 + ((i - 1) / 3 * 3 + (j - 1) / 3) * 9 + k);

其余的就可以直接写板子了。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5000;

int n , m , t , sum , cnt , tot , a[15][15];
int l[maxn] , r[maxn] , u[maxn] , d[maxn] , h[maxn] , qx[maxn] , qy[maxn] , vy[maxn] , ans[maxn];


inline int read()
{
    int s = 0 , f = 1; char ch;
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) s = s * 10 + ch - '0' , ch = getchar();
    return s * f;
}

inline void init()
{
    memset(l , 0 , sizeof(l));
    memset(r , 0 , sizeof(r));
    memset(d , 0 , sizeof(d));
    memset(u , 0 , sizeof(u));
    memset(h , -1 , sizeof(h));
    for(int i = 0;i <= m;i++)
    {
        l[i] = i - 1 , r[i] = i + 1;
        d[i] = u[i] = i;
    }
    tot = 0 , cnt = m + 1 , l[0] = m , r[m] = 0;
    memset(vy , 0 , sizeof(vy));
    memset(qx , 0 , sizeof(qx));
    memset(qy , 0 , sizeof(qy));
    memset(ans , 0 , sizeof(ans));
}

inline void add(int x , int y)
{
    qx[cnt] = x , qy[cnt] = y , vy[y]++;
    u[cnt] = y , d[cnt] = d[y] , u[d[y]] = cnt , d[y] = cnt;
    if(h[x] < 0) h[x] = l[cnt] = r[cnt] = cnt;
    else r[cnt] = h[x] , l[cnt] = l[h[x]] , l[h[x]] = r[l[h[x]]] = cnt;
    cnt++;
}

inline void remove(int p)
{
    l[r[p]] = l[p] , r[l[p]] = r[p];
    for(int i = d[p];i != p;i = d[i])
        for(int j = r[i];j != i;j = r[j])
        {
            vy[qy[j]]--;
            u[d[j]] = u[j] , d[u[j]] = d[j];
        }
    return;
}

inline void resume(int p)
{
    for(int i = u[p];i != p;i = u[i])
        for(int j = l[i];j != i;j = l[j])
        {
            vy[qy[j]]++;
            u[d[j]] = d[u[j]] = j;
        }
    l[r[p]] = r[l[p]] = p;
    return;
}

inline void dfs()
{
    if(!r[0])
    {
        sum++;
        for(int i = 1;i <= tot;i++)
            a[(ans[i] - 1) / 81 + 1][(ans[i] - 1) / 9 % 9 + 1] = (ans[i] - 1) % 9 + 1;
    }
    int p = r[0];
    for(int i = r[0];i;i = r[i])
        if(vy[p] > vy[i]) p = i;
    remove(p);
    for(int i = d[p];i != p;i = d[i])
    {
        ans[++tot] = qx[i];
        for(int j = r[i];j != i;j = r[j]) remove(qy[j]);
        dfs();
        for(int j = l[i];j != i;j = l[j]) resume(qy[j]);
        tot--;
    }
    resume(p);
}

int main()
{
    // freopen("1.in" , "r" , stdin);
    t = read() , n = 729 , m = 324;
    while(t--)
    {
        sum = 0 , init();
        for(int i = 1;i <= 9;i++)
        {
            for(int j = 1;j <= 9;j++)
            {
                a[i][j] = read();
                for(int k = 1;k <= 9;k++)
                {
                    if(!a[i][j] || a[i][j] == k)
                    {
                        add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 0 + (i - 1) * 9 + j);
                        add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 1 + (i - 1) * 9 + k);
                        add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 2 + (j - 1) * 9 + k);
                        add(((i - 1) * 9 + j - 1) * 9 + k , 81 * 3 + ((i - 1) / 3 * 3 + (j - 1) / 3) * 9 + k);
                    }
                }
            }
        }
        dfs();
        cout << sum << endl;
        if(sum == 1)
        {
            for(int i = 1;i <= 9;i++)
            {
                for(int j = 1;j <= 9;j++)
                    cout << a[i][j] << " ";
                cout << endl;
            }
        }
    }
    return 0;
}

码农公寓

DLX