题目背景

本题是舞蹈链模板——精确覆盖问题

题目描述

给定一个N行M列的矩阵，矩阵中每个元素要么是1，要么是0

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列j，在你挑选的这些行中，有且仅有一行的第j个元素为1

输入输出格式

输入格式：

第一行两个数N,M

接下来N行，每行M个数字0或1，表示这个矩阵

输出格式：

一行输出若干个数表示答案，两个数之间用空格隔开，输出任一可行方案均可，顺序随意

若无解，输出“No Solution!”（不包含引号）

输入输出样例

输入样例#1：

3 30 0 11 0 00 1 0

输出样例#1：

2 1 3

输入样例#2：

3 31 0 11 1 00 1 1

输出样例#2：

No Solution!

说明

N,M≤500

保证矩阵中1的数量不超过5000个

代码

舞蹈链板子题，维护矩阵，用双向链表支持删除恢复（回溯）操作

已选集合列点权为1，则删除所有该列点权为1的集合。

 

#include
       
        using namespace std;const int maxn=300000+10;int l[maxn],r[maxn],u[maxn],d[maxn];//左右上下指针，所在行列int col[maxn],row[maxn];//所在行列 int h[maxn];//每行表头 int s[maxn];//每列点数 int ans[maxn];int cnt;int n,m;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}void init(){    for(int i=0;i<=m;i++)    r[i]=i+1,l[i]=i-1,u[i]=d[i]=i;    r[m]=0;    l[0]=m;    cnt=m;}void insert(int R,int C)//行列 {        s[C]++;    row[++cnt]=R,col[cnt]=C;    u[cnt]=C,d[cnt]=d[C],u[d[cnt]]=cnt,d[C]=cnt;//双向链表实现     if(!h[R])h[R]=r[cnt]=l[cnt]=cnt;    else r[cnt]=h[R],l[cnt]=l[r[cnt]],r[l[cnt]]=cnt,l[r[cnt]]=cnt; }void remove(int C){    r[l[C]]=r[C],l[r[C]]=l[C];    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],s[col[j]]--;}void resume(int C){    for(int i=u[C];i!=C;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[C]]=C,l[r[C]]=C;}void dance(int dep){    if(r[0]==0)     {        for(int i=0;i