精确覆盖问题

解题思路

本题是一个经典的精确覆盖问题，是 $Dancing~Links$ 的模板题，直接套模板做即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5510;

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], top; //存储选择方案

void init() //初始化十字链表
{
    for(int i = 0; i <= m; i++) //初始化第一行的哨兵（表头）
    {
        l[i] = i - 1, r[i] = i + 1;
        u[i] = d[i] = i; //最开始只有一行，所有每个节点的上、下指针都指向自己
    }
    l[0] = m, r[m] = 0; //特别处理左、右边界情况
    idx = m + 1; //已经加入 m + 1 个节点，下标从 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; //横向：将当前节点插入 hh 和 tt 的中间
    tt = idx++; //tt 移到当前节点上，保证 hh 和 tt 之间仍是空的，方便后面插入
}

void remove(int p) //删除第 p 列
{
    r[l[p]] = r[p], l[r[p]] = l[p]; //将第 p 列的表头删掉
    for(int i = d[p]; i != p; i = d[i]) //将第 p 列是 1 的所有行删去
        for(int j = r[i]; j != i; j = r[j])
        {
            s[col[j]]--; //更新对应列中 1 的个数
            u[d[j]] = u[j], d[u[j]] = d[j]; //将该行在纵向意义上删去
        }
}

void resume(int p) //恢复第 p 列
{
    //根据删除操作完全反着来即可
    for(int i = u[p]; i != p; i = u[i])
        for(int j = l[i]; j != i; j = l[j])
        {
            u[d[j]] = j, d[u[j]] = j;
            s[col[j]]++;
        }
    r[l[p]] = p, l[r[p]] = p;
}

bool dfs() //dfs 求精确覆盖问题
{
    if(!r[0]) return true; //如果所有列都被删除，说明已经找到答案

    //否则还需要继续搜索，找出 1 的个数最少的列
    int p = r[0]; //记录 1 的个数最少的列的表头
    for(int i = r[0]; i; i = r[i])
        if(s[i] < s[p])
            p = i;

    remove(p); //将这一列删掉

    for(int i = d[p]; i != p; i = d[i]) //枚举当前列选择哪一行
    {
        res[++top] = row[i]; //将当前行加入答案
        for(int j = r[i]; j != i; j = r[j]) remove(col[j]); //将当前行中所有是 1 的列删去
        if(dfs()) return true; //如果当前分支有解，直接回溯
        //否则需要恢复现场
        for(int j = l[i]; j != i; j = l[j]) resume(col[j]); //将当前行中删去的所有列恢复
        top--; //将当前行从答案中移出
    }

    resume(p); //恢复现场

    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 才建出来
        }
    }

    if(dfs()) //如果有解
    {
        for(int i = 1; i <= top; i++) printf("%d ", res[i]);
        puts("");
    }
    else puts("No Solution!");

    return 0;
}