DLX(舞蹈链)

DLX(dancing links)是一种优化的X算法，用于求解精确覆盖问题。

精确覆盖问题，及用一些由1-n组成的集合，从中选择一些集合，使得1-n每个整数正好出现过一次。

对于这种问题，最为朴素的算法就是X算法。虽然名字看起来比较奇怪，但是就是裸的暴力dfs，因此没什么好说的。

而DLX就是对于X算法的优化。当然，因为仅仅是优化，因此复杂度是O(能过)。

对于每一个集合，如果我们选择了它，那么我们就可以删除掉所有包含它包含的数的集合，因为显然这些集合都不能取了。因此，我们从1开始遍历到n，如果这一列还没有取，那么我们就选择一个覆盖了该列的集合，删除其他集合，并且删除掉这个集合的所覆盖的所有列。到最后如果所有列都被删除掉了，那么这就是一个可行解，否则就进行回溯，而DLX算法就是优化了删除列的效率。

算法流程：

我们首先将所有集合转化为01的形式，表示是否覆盖了第i列，然后我们只将1视为节点并在每一列上方建立一个虚拟节点，同时在虚拟节点的最左侧再添加一个虚拟节点0，将每个节点指向其上下左右的节点（最左指向最右，最右指向最左，最上指向最下，最下指向最上），这样，我们在删除时就只需要修改双向链表的指向了。最后，我们只需要判断虚拟节点0的右侧是否还有节点即可。

DLX算法整体是十分简单清晰的，就是将节点转换成为了链表，加速了删除和恢复的速度。此外还有一个优化：每次删除列时优先删除被覆盖的集合数最少的列，这个优化就十分显然了。

具体的实现就上代码吧（参考例题：【模板】舞蹈链（DLX））：

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, cnt, sum, ans[505], num[505], s[505][505];
struct node
{
    int l;
    int r;
    int u;
    int d;
    int row;
    int col;
} a[250005];
void init()
{
    for (int i = 0; i <= m; ++i)
    {
        a[i].l = i - 1;
        a[i].r = i + 1;
        a[i].u = i;
        a[i].d = i;
    }
    a[0].l = m;
    a[m].r = 0;
    cnt = m + 1;
    return;
}
void add(int k)
{
    int first = cnt;
    for (int i = 1; i <= m; ++i)
        if (s[k][i])
        {
            a[cnt].l = cnt - 1;
            a[cnt].r = cnt + 1;
            a[cnt].u = a[i].u;
            a[cnt].d = i;
            a[a[cnt].u].d = cnt;
            a[i].u = cnt;
            a[cnt].row = k;
            a[cnt].col = i;
            ++num[i];
            ++cnt;
        }
    a[cnt - 1].r = first;
    a[first].l = cnt - 1;
    return;
}
void remove(int k)
{
    a[a[k].l].r = a[k].r;
    a[a[k].r].l = a[k].l;
    for (int i = a[k].d; i != k; i = a[i].d)
        for (int j = a[i].r; j != i; j = a[j].r)
        {
            a[a[j].u].d = a[j].d;
            a[a[j].d].u = a[j].u;
            --num[a[j].col];
        }
    return;
}
void restore(int k)
{
    for (int i = a[k].u; i != k; i = a[i].u)
        for (int j = a[i].l; j != i; j = a[j].l)
        {
            a[a[j].d].u = j;
            a[a[j].u].d = j;
            ++num[a[j].col];
        }
    a[a[k].l].r = k;
    a[a[k].r].l = k;
    return;
}
bool dfs(int k)
{
    if (a[0].r == 0)
    {
        sum = k;
        return true;
    }
    int mi = a[0].r;
    for (int i = a[0].r; i != 0; i = a[i].r)
        if (num[i] < num[mi])
            mi = i;
    remove(mi);
    for (int i = a[mi].d; i != mi; i = a[i].d)
    {
        ans[k + 1] = a[i].row;
        for (int j = a[i].r; j != i; j = a[j].r)
            remove(a[j].col);
        if (dfs(k + 1))
            return true;
        for (int j = a[i].l; j != i; j = a[j].l)
            restore(a[j].col);
    }
    restore(mi);
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &s[i][j]);
    for (int i = 1; i <= n; ++i)
        add(i);
    if (dfs(0))
        for (int i = 1; i <= sum; ++i)
            printf("%d ", ans[i]);
    else
        puts("No Solution!");
    return 0;
}