hihocoder 1317 (DLX cover precisely)

Description

小Ho最近遇到一个难题，他需要破解一个棋局。

棋局分成了n行，m列，每行有若干个棋子。小Ho需要从中选择若干行使得每一列有且恰好只有一个棋子。

http://hihocoder.com/problemset/problem/1317

Dancing Link X

https://www.cnblogs.com/grenet/p/3145800.html

Dancing Links : 循环双向链，纵横交叉形成的网状结构

Code

#include <cstdio>
#include <iostream>
using namespace std;
const int MAX_V = 10010;


int n, m;
int cnt[105];///第i列1元素的个数
int L[MAX_V], R[MAX_V], U[MAX_V], D[MAX_V];
int Head[105];///第i行第一个1元素的ID,意义同列标元素
int Row[MAX_V], Col[MAX_V];///记录id所在行列
int ans[105];


void init()
{
    for(int i = 0; i <= m; ++i)///初始化Head及m个列标元素
    {
        cnt[i] = 0;
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = i;
        D[i] = i;
    }

    L[0] = m;
    R[m] = 0;

    for(int i = 0; i <= n; ++i)///初始化“伪行标元素”
        Head[i] = -1;
}

void link(int row, int col, int id)
{
    Row[id] = row;
    Col[id] = col;

    U[id] = U[col];///我向上
    D[id] = col;///我向下
    D[ U[col] ] = id;///我上 下我
    U[col] = id;///我下 上我

    if(Head[row] == -1)
        Head[row] = L[id] = R[id] = id;
    else
    {
        L[id] = L[ Head[row] ];///我向左
        R[id] = Head[row];///我向右
        R[ L[ Head[row] ] ] = id;///我左 右我
        L[ Head[row] ] = id;///我右 左我
    }

    cnt[col]++;
}

void abandon(int c)
{
    ///抛弃c列
    L[ R[c] ] = L[c];///我右的左 在将来 就是现在的 我左
    R[ L[c] ] = R[c];

    ///抛弃c列1元素所在行(∵不能同时选)
    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];
            --cnt[ Col[j] ];
        }
}

void resume(int c)
{
    ///恢复c列1元素所在行
    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;
            ++cnt[ Col[j] ];
        }

    ///列标元素
    L[ R[c] ] = R[ L[c] ] = c;
}

bool Dance(int deep)
{
    if(R[0] == 0)
        return 1;

    ///找到1的数目最少的一列  将列标元素存在c里
    int c = R[0];
    for(int i = R[0]; i != 0; i = R[i])
        if(cnt[i] < cnt[c])
            c = i;

    abandon(c);

    ///对于c列1元素所在行，遍历每行，看看选择哪一行合适
    for(int i = D[c]; i != c; i = D[i])
    {
        ans[deep] = Row[i];///选当前行
        for(int j = R[i]; j != i; j = R[j])
            abandon(Col[j]);///删除1元素所在行上 1元素所在列
        if(Dance(deep + 1))
            return 1;

        for(int j = L[i]; j != i; j = L[j])
            resume(Col[j]);
    }

    resume(c);

    return 0;
}

int main()
{
    int _, val, id;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d%d", &n, &m);
        init();
        id = m;///0->Head, [1, m]对应列标元素
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                scanf("%d", &val);
                if(val)
                {
                    id++;
                    link(i, j, id);
                }
            }
        if(Dance(0))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}