Dancing Link X 求精确覆盖与重复覆盖入门

DLX算法入门文……主要说一下我对这个算法的理解。

问题描述

精确覆盖问题：

以矩阵模型介绍，给你一个矩阵，其每个格子的权值范围是 [0,1] ，让你选出若干行，使得选出的行的 1 覆盖了一行的所有格子，且不能有重叠。

重复覆盖问题：

与精确覆盖问题基本相同，但是所选的行集合中，同一列的 1 允许重叠。
这个问题当然不可能让你输出可行方案，输出的应该是行数最小的方案。

算法理解

精确覆盖和重复覆盖都是NP问题，通常的，我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客，里面讲的非常详细，一般人写的博客已然不会超过他。
所以我写这个个人理解其实主要是给自己看的。

首先最容易的当然是 ( 2^{row} ) 的最简单的裸搜，这谁都想得到……而且复杂度很高……

其实当我们选中一行时，对于这一行的每一个 1 元素，含有与选中行同一列的 1 元素的行自然是不能选的，与此同时对于选中行每一个 1 元素，它所在的列其实我们也已经不再需要去考虑它们，因此，我们可以把这些元素删除，得到一个新的矩阵，如此重复操作，直到能覆盖一行的所有格子。

基本的原理就是这些，因为涉及到非常多的增删数据，使用链表是非常非常高效且合理的！！
因为给定的图一般是稀疏图，所以如果只记录 1 的位置将会非常省内存。

而对于重复覆盖，与精确覆盖基本一致，因为找最小的原因，还可以加一个 A * 优化。

入门实践与模板

HihoCoder 1317 搜索四·跳舞链

题意：
最基本的精确覆盖入门题

思路：
模板题……

而且非常意外的发现网上的模板相似度非常高！！
所以我这里也就改了一蛤变量名就没了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string.h>
#include <string>
#include <utility>
#include <vector>

#define ll long long

using namespace std;

const int maxnode = 1e5 + 10;
const int maxm = 1e3 + 5;
const int maxn = 1e3 + 5;

struct DLX {
    int n, m, size;
    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; //L,R,D,U四个数组记录某节点上下左右邻居
    int head[maxn], ccnt[maxm];                                                     //head记录排头，ccnt记录某列有多少个节点
    int ansd, ans[maxn];
    void init(int _n, int _m)
    {
        n = _n;
        m = _m;
        for (int i = 0; i <= m; i++) {
            ccnt[i] = 0;
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        R[m] = 0;
        L[0] = m;
        size = m;
        for (int i = 1; i <= n; i++)
            head[i] = -1;
    }

    void link(int r, int c)
    {
        ++ccnt[Col[++size] = c];
        Row[size] = r;
        D[size] = D[c];
        U[D[c]] = size;
        U[size] = c;
        D[c] = size;
        if (head[r] < 0)
            head[r] = L[size] = R[size] = size;
        else {
            R[size] = R[head[r]];
            L[R[head[r]]] = size;
            L[size] = head[r];
            R[head[r]] = size;
        }
    }

    void exactRemove(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];
                --ccnt[Col[j]];
            }
    }

    void repeatRemove(int c)
    {
        for (int i = D[c]; i != c; i = D[i])
            L[R[i]] = L[i], R[L[i]] = R[i];
    }

    void repeatResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            L[R[i]] = R[L[i]] = i;
    }

    int f()
    {
        bool vv[maxm];
        int ret = 0, c, i, j;
        for (c = R[0]; c != 0; c = R[c])
            vv[c] = 1;
        for (c = R[0]; c != 0; c = R[c])
            if (vv[c]) {
                ++ret, vv[c] = 0;
                for (i = D[c]; i != c; i = D[i])
                    for (j = R[i]; j != i; j = R[j])
                        vv[Col[j]] = 0;
            }
        return ret;
    }

    void repeatDance(int d)
    {
        if (d + f() >= ansd)
            return; //估价函数剪枝，A*搜索
        if (R[0] == 0) {
            if (d < ansd)
                ansd = d;
            return;
        }
        int c = R[0], i, j;
        for (i = R[0]; i; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        for (i = D[c]; i != c; i = D[i]) {
            repeatRemove(i);
            for (j = R[i]; j != i; j = R[j])
                repeatRemove(j);
            repeatDance(d + 1);
            for (j = L[i]; j != i; j = L[j])
                repeatResume(j);
            repeatResume(i);
        }
    }

    void exactResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                ++ccnt[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    //d为递归深度
    bool exactDance(int d)
    {
        if (R[0] == 0) {
            ansd = d;
            return true;
        }
        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        exactRemove(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])
                exactRemove(Col[j]);
            if (exactDance(d + 1))
                return true;
            for (int j = L[i]; j != i; j = L[j])
                exactResume(Col[j]);
        }
        exactResume(c);
        return false;
    }

    void output()
    {
        printf("%d", ansd);
        for (int i = 0; i < ansd; i++)
            printf(" %d", ans[i]);
        puts("");
    }
};

DLX dlx;
int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        dlx.init(n, m);
        for (int i = 1, num; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &num);
                if (num == 1)
                    dlx.link(i, j);
            }
        if (!dlx.exactDance(0))
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}