精确覆盖和重复覆盖

标签：11 输出 覆盖 重复 矩阵 复制 精确 include

精确覆盖

给定一个 �N 行 �M 列的矩阵，矩阵中每个元素要么是 11，要么是 00。

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

输入格式

第一行两个数 �,�N,M。

接下来 �N 行，每行 �M 个数字 00 或 11，表示这个矩阵。

输出格式

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

若无解，输出 No Solution!。

输入输出样例

输入 #1复制

3 3
0 0 1
1 0 0
0 1 0

输出 #1复制

2 1 3

输入 #2复制

3 3
1 0 1
1 1 0
0 1 1

输出 #2复制

No Solut

P4929 【模板】舞蹈链（DLX） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
舞蹈链

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=250501;//n*m+m<=250500
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m;
int cnt;
int l[mx],r[mx],u[mx],d[mx],col[mx],row[mx];//每个点的左右上下指针，所在行列 
int h[mx];//每行的头结点 
int s[mx];//每列的节点数 
int ansk[mx];//选了那些集合 
void init(int m){//m个元素 
    for(register 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;
    memset(h,-1,sizeof(h));
    memset(s,0,sizeof(s));
    cnt=m+1;
}//初始化 
inline void link(int R,int C){//R行C列插入点 
    s[C]++;
    row[cnt]=R;
    col[cnt]=C;
    u[cnt]=C;
    d[cnt]=d[C];
    u[d[C]]=cnt;
    d[C]=cnt;
    if(h[R]==-1)h[R]=r[cnt]=l[cnt]=cnt;//该行没有点，直接加入 
    else{
        r[cnt]=h[R];
        l[cnt]=l[h[R]];
        r[l[h[R]]]=cnt;
        l[h[R]]=cnt;
    }
    cnt++;
    return;
}
inline void remove(int C){//删除涉及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]]--;
        }
    }
}
inline void resume(int C){//恢复涉及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;
}
bool dance(int deep){
    if(r[0]==0){
        register int i=0;
        for(i=0;i<deep;i++)printf("%d ",ansk[i]);
        return 1;
    }
    int c=r[0];
    int i,j;
    for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
    remove(c);
    for(i=d[c];i!=c;i=d[i]){
        ansk[deep]=row[i];
        for(j=r[i];j!=i;j=r[j])remove(col[j]);
        if(dance(deep+1))return 1;
        for(j=l[i];j!=i;j=l[j])resume(col[j]);
    }
    resume(c);
    return 0;
}
int main(){
//    freopen("cin.txt","r",stdin);
    n=Read(),m=Read();
    register int i,j;
    int f;
    init(m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            f=Read();
            if(f)link(i,j);
        }
    }
    if(!dance(0))printf("No Solution!");
    return 0;
}

重复覆盖

 

标签：11,输出,覆盖,重复,矩阵,复制,精确,include
From： https://www.cnblogs.com/weinan030416/p/17060687.html