ZOJ 3209 Treasure Map (DLX)

2023-10-13 04:58
文章标签 map zoj 3209 treasure dlx

本文主要是介绍ZOJ 3209 Treasure Map (DLX),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:

思路:

DLX的精确覆盖
这道题让我明白了DLX的大体思路方向,就是把问题转化成一种类似二分图匹配的问题,想办法建立出行和列,使之产生可匹配的关系
对于这个题,每个矩阵都对应原大矩阵的一些面积,我们给原矩阵每块面积都标号,这样形成了对应关系,就可以用DLX精确覆盖了

错误及反思:

代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
//精确覆盖问题的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得集合中每一列都恰好包含一个1
const int MN = 1005;//最大行数
const int MM = 1005;//最大列数
const int MNN = 1e5 + 5 + MM; //最大点数struct DLX
{int n, m, si;//n行数m列数si目前有的节点数//十字链表组成部分int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN];//第i个结点的U向上指针D下L左R右,所在位置Row行Col列int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况int ansd, ans[MN];void init(int _n, int _m)  //初始化空表{n = _n;m = _m;for (int i = 0; i <= m; i++) //初始化第一横行(表头){U[i] = D[i] = i;      //目前纵向的链是空的L[i] = i - 1;R[i] = i + 1;         //横向的连起来}R[m] = 0; L[0] = m;si = m;                 //目前用了前0~m个结点memset(S, 0, sizeof(S));memset(H, -1, sizeof(H));}void link(int r, int c)    //插入点(r,c){++S[Col[++si] = c];     //si++;Col[si]=c;S[c]++;Row[si] = r;//si该结点的行数为rD[si] = D[c];//向下指向c的下面的第一个结点U[D[c]] = si;//c的下面的第一个结点的上面为siU[si] = c;//si的上面为列指针D[c] = si;//列指针指向的第一个该列中的元素设为siif (H[r]<0)//如果第r行没有元素H[r] = L[si] = R[si] = si;else{R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为siL[si] = H[r];//si的左侧为行指针R[H[r]] = si;//行指针的右侧为si}}void remove(int c)        //列表中删掉c列{L[R[c]] = L[c];//表头操作  //c列头指针的右边的元素的左侧指向c列头指针左边的元素R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向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)        //恢复c列{for (int i = U[c]; i != c; i = U[i])//枚举该列元素for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++;L[R[c]] = R[L[c]] = c;//c列头指针左右相连}bool dance(int d) //选取了d行{if (ansd != -1 && ansd < d)return 0;if (R[0] == 0)//全部覆盖了{//全覆盖了之后的操作if(ansd==-1)ansd = d;else if (d < ansd) ansd = d;return 1;}int c = R[0];//表头结点指向的第一个列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]);//将该列的某个元素的行上的元素所在的列都删去dance(d + 1);for (int j = L[i]; j != i; j = L[j])resume(Col[j]);}resume(c);return 0;}
}dlx;
inline int read() {char ch = getchar(); int x = 0, f = 1;while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();} while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} return x * f;
}
int main()
{int T;T=read();while(T--){int n, m, k;n=read();m=read();k=read();dlx.init(k-1 ,n*m );for(int i=0;i<k;i++){int x1,x2,y1,y2;x1=read();y1=read();x2=read();y2=read();for(int j=x1;j<x2;j++)for(int l=y1;l<y2;l++)dlx.link(i,j*m+l+1);}dlx.ansd=-1;dlx.dance(0);printf("%d\n", dlx.ansd);}
}

这篇关于ZOJ 3209 Treasure Map (DLX)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/200911

相关文章

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式,允

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》:本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历:2、Java8 Stream API:3、Apache Commons

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

zoj 4624

题目分析:有两排灯,每排n个,每个灯亮的概率为p,每个灯之间互不影响,亮了的灯不再灭,问两排中,每排有大于等于m个灯亮的概率。 设dp[ i ][ j ]为第一排亮了i个灯,第二排亮了j个灯,距离目标状态的期望天数。显然 i >= m ,j >= m时 , dp[ i ][ j ] = 0 。 状态转移 : 第一排亮了a个灯,a 在[ 0 , n - i] 之间,第二排亮了b个灯 , b 在