FZU 1686 神龙的难题(DLX repeat cover)

Deacription

N x M的01矩阵，给出a、b，表示一次性可以将a行b列的小矩阵内的数字全变成0，问最终使全图为0需要几步

建模

把每个1视为列，每一种覆盖方式视为行

最少需要拿出多少行，使得每列都含有1——重复覆盖

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 100005;///数组开小可能超时


int n, m, length, width, res, tot;
int cnt[255];///第i列1元素的个数
int L[MAX_V], R[MAX_V], U[MAX_V], D[MAX_V];
int Head[255];///第i行第一个1元素的ID,意义同列标元素
int Row[MAX_V], Col[MAX_V];///记录id所在行列
int ans[255], mp[20][20];
bool vis[255];

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

    L[0] = tot;
    R[tot] = 0;

    memset(Head, -1, sizeof(Head));
}

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]++;
}

///具体删除列，没有删除行(这一列有1了，我以后无需参考此列选行)
void abandon(int id)
{
    for(int i = D[id]; i != id; i = D[i])///空了id,便于后续删除列
        L[ R[i] ] = L[i], R[ L[i] ] = R[i];
}

void resume(int id)
{
    for (int i = D[id]; i != id; i = D[i])///空了id(因为上面就没abandon)
        L[ R[i] ] = R[ L[i] ] = i;
}

int h()
{
    int num = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = R[0]; i != 0; i = R[i])
    {
        if(vis[i])
            continue;
        num++;
        for(int j = D[i]; j != i; j = D[j])
            for(int k = R[j]; k != j; k = R[k])
                vis[ Col[k] ] = 1;
    }
    return num;///当前矩阵可拆解次数
}


void Dance(int deep)
{
    if(deep + h() >= res)///估价剪枝
        return ;

    if(R[0] == 0)///准出口(每次abandon都会ban掉列标元素)
    {
        if(deep < res)
            res = deep;
        return;
    }

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

    ///对于c列1元素所在行，遍历每行，看看选择哪一行合适
    ///最少含1列，1所在行必然不被同时选
    for(int i = D[c]; i != c; i = D[i])
    {
        ans[deep] = Row[i];///选当前行

        abandon(i);///我选这个1,后续无需参考此列(删除)
        for(int j = R[i]; j != i; j = R[j])
            abandon(j);///删除1元素所在行上 1元素所在列

        Dance(deep + 1);

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

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        tot = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                scanf("%d", &mp[i][j]);
                if(mp[i][j])
                    mp[i][j] = ++tot;
            }
        int id = tot, block = 0;
        init();
        scanf("%d%d", &length, &width);
        for(int i = 1; i + length - 1 <= n; ++i)
            for(int j = 1; j + width - 1 <= m; ++j)
            {
                block++;
                for(int k = i; k <= i + length - 1; ++k)
                    for(int l = j; l <= j + width - 1; ++l)
                        if(mp[k][l])
                            link(block, mp[k][l], ++id);
            }
        res = 0x3f3f3f3f;///不要自以为是随便搞
        Dance(0);
        cout << res << '\n';
    }
    return 0;
}