博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
跳舞链 (DLX)模板。。
阅读量:6647 次
发布时间:2019-06-25

本文共 2610 字,大约阅读时间需要 8 分钟。

 

 
#define CL(a,num) memset((a),(num),sizeof(a))#define inf 0x7f7f7f7f#define M 1007#define N 1000007const int head = 0;int u[N],d[N],l[N],r[N],c[N],row[N];int s[M],o[M];int ak,n,m;void init(int m){    int i;    for (i = 1; i <= m; ++i){        l[i] = i - 1;        r[i] = i + 1;        u[i] = d[i] = i;        c[i] = i;        s[i] = 0;    }    l[head] = m; r[head] = 1;    r[m] = head;}void remove(int ci){    int i,j;    l[r[ci]] = l[ci];    r[l[ci]] = r[ci];    for (i = d[ci]; i != ci; i = d[i]){        for (j = r[i]; j != i; j = r[j]){            u[d[j]] = u[j];            d[u[j]] = d[j];            s[c[j]]--;        }    }}void resume(int ci){    int i,j;    l[r[ci]] = r[l[ci]] = ci;    for (i = u[ci]; i != ci; i = u[i]){        for (j = l[i]; j != i; j = l[j]){            u[d[j]] = d[u[j]] = j;            s[c[j]]++;        }    }}int dfs(int k){    int i,j;    //若列对象为空,说明所有列已经覆盖,返回值    if (r[head] == head){        ak = k;        return 1;    }    //每次着该列里面1最少的    int MIN = inf, ci = 0;    for (i = r[head]; i != head; i = r[i]){        if (s[i] < MIN){            MIN = s[i];            ci = i;        }    }    remove(ci);//删除该列对象以及该列所覆盖的行    for (i = d[ci]; i != ci; i = d[i]){        for (j = r[i]; j != i; j = r[j]){            remove(c[j]);//选择i作为覆盖c列的行,并且要删调该行所覆盖的列        }        o[k] = row[i];//记录结果        if (dfs(k + 1)) return 1;//继续选择列    //i列不能满足还原i列        for (j = l[i]; j != i; j = l[j]){            resume(c[j]);        }    }    resume(ci);    return 0;}int main(){    int i,j;    int num,size;    while (~scanf("%d%d",&n,&m)){      //更新列对象       init(m);        size = m + 1;//记录第几个        int x;        for (i = 0; i < n; ++i){            scanf("%d",&num);            int rh = -1;            for (j = 0; j < num; ++j){                scanf("%d",&x);                s[x]++;//记录x列有多少个1                c[size] = x;//记录第size个的列                row[size] = i + 1;//记录第size个的行        //插入列,挂链                u[size] = u[x];                d[u[x]] = size;                u[x] = size;                d[size] = x;        //插入行,挂链                if (rh == -1){                    l[size] = r[size] = size;                    rh = size;                }                else{                    l[size] = l[rh];                    r[l[rh]] = size;                    l[rh] = size;                    r[size] = rh;                }                size++;            }        }        if (dfs(0)){            printf("%d",ak);            for (i = 0; i < ak; ++i) printf(" %d",o[i]);            printf("\n");        }        else{            printf("NO\n");        }    }    return 0;}
 

  

  

转载地址:http://obuto.baihongyu.com/

你可能感兴趣的文章
自定义的allocator
查看>>
浅谈CSRF漏洞
查看>>
JS----基本数据类型
查看>>
明天考前突击
查看>>
Android中的Handler的机制与用法详解
查看>>
【算法学习笔记】18.暴力求解法06 隐式图搜索2 八数码问题 未启发
查看>>
「小程序JAVA实战」运行微信官方demo(四)
查看>>
jqGrid基本用法与示例
查看>>
spring @Bean注解的使用
查看>>
Vmware Workstation及Centos6.8 的安装
查看>>
发生未知错误17,解决办法
查看>>
EL与OGNL区别
查看>>
第7章课后总结
查看>>
Python os模块,常用函数和类
查看>>
C#窗体加载和控件加载不同步导致控件闪烁
查看>>
js 2
查看>>
PHP支付宝手机网站支付功能
查看>>
Lambda 表达式
查看>>
[杂谈]记第一次出差有感
查看>>
block的作用
查看>>