舞蹈链纯模板(kuangbin)hust1017_舞蹈链算法模板hst-程序员宅基地

技术标签: 舞蹈链 kuangbin  acm  编程  ==数据结构==  数据结构  

//  main.cpp

//  舞蹈链 舞蹈链纯模板(kuangbin)hust1017

//  Created by liuzhe on 16/11/30.

//  Copyright 2016 my_code. All rights reserved.

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int maxnode = 100010;

const int MaxM = 1010;

const int MaxN = 1010;

struct DLX

{

    int n,m,size;

    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];

    //U D R L用来记录某个标号的节点的上下左右节点的标号

    //Row Col用来记录某个标号的节点在矩阵中的行号和列号

    int H[MaxN], S[MaxM];

    //H是行头 S用来保存某一列中1的数量

    int ansd, ans[MaxN];

    void init(int _n,int _m)

    {

        n = _n;

        m = _m;

        //初始化列头

        for(int i = 0;i <= m;i++)

        {

            S[i] = 0;

            U[i] = D[i] = i;

            L[i] = i-1;

            R[i] = i+1;

        }

        R[m] = 0; L[0] = m;

        size = m;

        for(int i = 1;i <= n;i++)

            H[i] = -1;

    }

    void Link(int r,int c)

    {

        ++S[Col[++size]=c];

        Row[size] = r;

        D[size] = D[c];

        U[D[c]] = size;

        U[size] = c;

        D[c] = size;

        if(H[r] < 0)H[r] = L[size] = R[size] = size;

        else

        {

            R[size] = R[H[r]];

            L[R[H[r]]] = size;

            L[size] = H[r];

            R[H[r]] = size;

        }

    }

    //对某一列进行删除 同时删除列中为1的行

    void remove(int c)

    {

        L[R[c]] = L[c]; R[L[c]] = R[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]]=D[U[j]]=j;

                ++S[Col[j]];

            }

        L[R[c]] = R[L[c]] = c;

    }

    //d为递归深度

    bool Dance(int d)

    {

        if(R[0] == 0)

        {

            ansd = d;

            return true;

        }

        int c = R[0];

        //一个优化  找到列中包含1最多的列 因为这样有助于减少递归深度 (很显然1多了 删掉的行也多 矩阵缩小得就快)

        for(int i = R[0];i != 0;i = R[i])

            if(S[i] < S[c])

                c = i;

        remove(c);

        //搜索

        for(int i = D[c];i != c;i = D[i])

        {

            ans[d] = Row[i];

            for(int j = R[i]; j != i;j = R[j])remove(Col[j]);

            if(Dance(d+1))return true;

            for(int j = L[i]; j != i;j = L[j])resume(Col[j]);

        }

        resume(c);

        return false;

    }

};


DLX g;

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,m;

    while(scanf("%d%d",&n,&m) == 2)

    {

        g.init(n,m);

        for(int i = 1;i <= n;i++)

        {

            int num,j;

            scanf("%d",&num);

            while(num--)

            {

                scanf("%d",&j);

                g.Link(i,j);

            }

        }

        if(!g.Dance(0))printf("NO\n");

        else

        {

            printf("%d",g.ansd);

            for(int i = 0;i < g.ansd;i++)

                printf(" %d",g.ans[i]);

            printf("\n");

        }

    }

    return 0;

}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/The_star_is_at/article/details/53408726

智能推荐

hdu 1229 还是A+B(水)-程序员宅基地

文章浏览阅读122次。还是A+BTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 24568Accepted Submission(s): 11729Problem Description读入两个小于10000的正整数A和B,计算A+B。...

http客户端Feign——日志配置_feign 日志设置-程序员宅基地

文章浏览阅读419次。HEADERS:在BASIC的基础上,额外记录了请求和响应的头信息。FULL:记录所有请求和响应的明细,包括头信息、请求体、元数据。BASIC:仅记录请求的方法,URL以及响应状态码和执行时间。NONE:不记录任何日志信息,这是默认值。配置Feign日志有两种方式;方式二:java代码实现。注解中声明则代表某服务。方式一:配置文件方式。_feign 日志设置

[转载]将容器管理的持久性 Bean 用于面向服务的体系结构-程序员宅基地

文章浏览阅读155次。将容器管理的持久性 Bean 用于面向服务的体系结构本文将介绍如何使用 IBM WebSphere Process Server 对容器管理的持久性 (CMP) Bean的连接和持久性逻辑加以控制,使其可以存储在非关系数据库..._javax.ejb.objectnotfoundexception: no such entity!

基础java练习题(递归)_java 递归例题-程序员宅基地

文章浏览阅读1.5k次。基础java练习题一、递归实现跳台阶从第一级跳到第n级,有多少种跳法一次可跳一级,也可跳两级。还能跳三级import java.math.BigDecimal;import java.util.Scanner;public class Main{ public static void main(String[]args){ Scanner reader=new Scanner(System.in); while(reader.hasNext()){ _java 递归例题

面向对象程序设计(荣誉)实验一 String_对存储在string数组内的所有以字符‘a’开始并以字符‘e’结尾的单词做加密处理。-程序员宅基地

文章浏览阅读1.5k次,点赞6次,收藏6次。目录1.串应用- 计算一个串的最长的真前后缀题目描述输入输出样例输入样例输出题解2.字符串替换(string)题目描述输入输出样例输入样例输出题解3.可重叠子串 (Ver. I)题目描述输入输出样例输入样例输出题解4.字符串操作(string)题目描述输入输出样例输入样例输出题解1.串应用- 计算一个串的最长的真前后缀题目描述给定一个串,如ABCDAB,则ABCDAB的真前缀有:{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有:{ B, AB,DAB, CDAB, BCDAB_对存储在string数组内的所有以字符‘a’开始并以字符‘e’结尾的单词做加密处理。

算法设计与问题求解/西安交通大学本科课程MOOC/C_算法设计与问题求解西安交通大学-程序员宅基地

文章浏览阅读68次。西安交通大学/算法设计与问题求解/树与二叉树/MOOC_算法设计与问题求解西安交通大学

随便推点

[Vue warn]: Computed property “totalPrice“ was assigned to but it has no setter._computed property "totalprice" was assigned to but-程序员宅基地

文章浏览阅读1.6k次。问题:在Vue项目中出现如下错误提示:[Vue warn]: Computed property "totalPrice" was assigned to but it has no setter. (found in <Anonymous>)代码:<input v-model="totalPrice"/>原因:v-model命令,因Vue 的双向数据绑定原理 , 会自动操作 totalPrice, 对其进行set 操作而 totalPrice 作为计..._computed property "totalprice" was assigned to but it has no setter.

basic1003-我要通过!13行搞定:也许是全网最奇葩解法_basic 1003 case 1-程序员宅基地

文章浏览阅读60次。十分暴力而简洁的解决方式:读取P和T的位置并自动生成唯一正确答案,将题给测点与之对比,不一样就给我爬!_basic 1003 case 1

服务器浏览war文件,详解将Web项目War包部署到Tomcat服务器基本步骤-程序员宅基地

文章浏览阅读422次。原标题:详解将Web项目War包部署到Tomcat服务器基本步骤详解将Web项目War包部署到Tomcat服务器基本步骤1 War包War包一般是在进行Web开发时,通常是一个网站Project下的所有源码的集合,里面包含前台HTML/CSS/JS的代码,也包含Java的代码。当开发人员在自己的开发机器上调试所有代码并通过后,为了交给测试人员测试和未来进行产品发布,都需要将开发人员的源码打包成Wa..._/opt/bosssoft/war/medical-web.war/web-inf/web.xml of module medical-web.war.

python组成三位无重复数字_python组合无重复三位数的实例-程序员宅基地

文章浏览阅读3k次,点赞3次,收藏13次。# -*- coding: utf-8 -*-# 简述:这里有四个数字,分别是:1、2、3、4#提问:能组成多少个互不相同且无重复数字的三位数?各是多少?def f(n):list=[]count=0for i in range(1,n+1):for j in range(1, n+1):for k in range(1, n+1):if i!=j and j!=k and i!=k:list.a..._python求从0到9任意组合成三位数数字不能重复并输出

ElementUl中的el-table怎样吧0和1改变为男和女_elementui table 性别-程序员宅基地

文章浏览阅读1k次,点赞3次,收藏2次。<el-table-column prop="studentSex" label="性别" :formatter="sex"></el-table-column>然后就在vue的methods中写方法就OK了methods: { sex(row,index){ if(row.studentSex == 1){ return '男'; }else{ return '女'; }..._elementui table 性别

java文件操作之移动文件到指定的目录_java中怎么将pro.txt移动到design_mode_code根目录下-程序员宅基地

文章浏览阅读1.1k次。java文件操作之移动文件到指定的目录_java中怎么将pro.txt移动到design_mode_code根目录下

推荐文章

热门文章

相关标签