重复覆盖问题

解题思路

本题是重复覆盖问题的模板，直接用 $Dancing~Links$ 求解即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10110;

int n, m;
//l[i] 表示节点 i 的左节点
//r[i] 表示节点 i 的右节点
//u[i] 表示节点 i 的上节点
//d[i] 表示节点 i 的下节点
//s[i] 表示第 i 列中 1 的个数
//row[i] 表示节点 i 所在的行的编号
//col[i] 表示节点 i 所在的列的编号
int l[N], r[N], u[N], d[N], s[N], row[N], col[N], idx;
int res[N]; //记录方案选择的所有行的编号
bool st[110]; //用于计算启发函数

void init() //初始化十字链表
{
    for(int i = 0; i <= m; i++)
    {
        l[i] = i - 1, r[i] = i + 1;
        col[i] = u[i] = d[i] = i;
        s[i] = 0;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}

void add(int &hh, int &tt, int x, int y) //将 (x, y) 加入到 hh 和 tt 之间
{
    row[idx] = x, col[idx] = y, s[y]++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = idx, l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx++;
}

int h() //估价函数：至少还要选多少行，使得每一列都有 1
{
    int cnt = 0; //记录最少要选的行数
    memset(st, 0, sizeof st); //清空 st，st 表示当前新覆盖了哪些列
    for(int i = r[0]; i; i = r[i]) //枚举当前还没有被覆盖的列
    {
        if(st[col[i]]) continue; //如果当前列已经被覆盖掉，直接跳过
        cnt++; //否则要选的行数 + 1
        st[col[i]] = true; //记录当前列被覆盖
        for(int j = d[i]; j != i; j = d[j]) //将这一列所有的行都选上
            for(int k = r[j]; k != j; k = r[k]) //将每一行中所有是 1 的列覆盖
                st[col[k]] = true; 
    }
    return cnt;
}

void remove(int p) //将 p 所在的列删掉（将这一列整个删掉但是保留 p，方便恢复）
{
    for(int i = d[p]; i != p; i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}

void resume(int p) //将 p 所在的列恢复
{
    for(int i = u[p]; i != p; i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}

bool dfs(int k, int depth) //迭代加深，k 表示当前已经选择的行数，depth 表示最多选择的行数
{
    //如果当前选择的行数 + 最少还要选择的行数 > 最多能选择的行数，说明无解
    if(k + h() > depth) return false;
    if(!r[0]) return true; //如果所有列都已经被覆盖，说明有解

    //否则找到 1 的个数最少的列继续搜索
    int p = r[0];
    for(int i = r[0]; i; i = r[i])
        if(s[i] < s[p])
            p = i;

    //枚举选择的行
    for(int i = d[p]; i != p; i = d[i])
    {
        res[k] = row[i];
        //将当前行中有 1 的列都删掉
        remove(i); //下面的循环删除时删不掉 i 所在的列，这里单独删一下
        for(int j = r[i]; j != i; j = r[j]) remove(j);
        if(dfs(k + 1, depth)) return true;
        //否则将删掉的列恢复
        for(int j = l[i]; j != i; j = l[j]) resume(j);
        //同理恢复时也恢复不到 i，单独恢复一下 i 所在的列
        resume(i);
    }
    return false; //到这说明当前分支无解
}

int main()
{
    scanf("%d%d", &n, &m);

    init(); //初始化十字链表

    //依次加入图中每一行
    for(int i = 1; i <= n; i++)
    {
        int hh = idx, tt = idx;
        for(int j = 1; j <= m; j++)
        {
            int x;
            scanf("%d", &x);
            if(x) add(hh, tt, i, j); //如果当前点是 1 就加入十字链表
        }
    }

    //迭代加深
    int depth = 0;
    while(!dfs(0, depth)) depth++;

    printf("%d\n", depth);
    for(int i = 0; i < depth; i++) printf("%d ", res[i]);

    return 0;
}