HDU-2295___Radar —— 二分 + DLX重复覆盖

2023-11-02 10:58

本文主要是介绍HDU-2295___Radar —— 二分 + DLX重复覆盖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:点我啊╭(╯^╰)╮

题目大意:

     n n n 个城市、 m m m 个雷达,最多可以用 k k k 个雷达,然后给出城市和雷达的坐标,要求雷达的最小覆盖半径,使得所有城市都被雷达覆盖???

解题思路:

    很清晰是一道DLX重复覆盖的题,本题的精度要精确到 1 e − 8 1e-8 1e8,所以只能用二分,二分的可行性判断是所用的雷达数是否 ≤ k ≤k k
    本题建造 01 01 01 矩阵比较简单,横坐标就是雷达,纵坐标为城市,雷达与城市之间的距离若 ≤ m i d ≤mid mid,则该点为 1 1 1

代码思路:

    主要还是重复覆盖的模板题,注意是用了 A* 的优化,估价函数 f f f 意义为从当前状态最好情况下需要添加几条边才能覆盖

核心:二分 + DLX 的简单题,同时注意精度

P S : PS: PS本题的 dfs 返回值可以为 b o o l bool bool,因为可以用当前深度与 k k k 进行比较

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;struct DancingLink{const static int N = 500010;const static int M = 1010;int n, s, ansd;	// 列数 节点总数 int S[M], A[M], H[M];	// S[]该列节点总数  A[]答案  H[]行首指针 int L[N], R[N], U[N], D[N];	// L[],R[],U[],D[] 上下左右 int X[N], C[N], vis[M];	// X[] C[] 行列编号 void init(int n){	// 初始化 this->n = n;for(int i=0; i<=n; i++)U[i]=i, D[i]=i, L[i]=i-1, R[i]=i+1;R[n]=0, L[0]=n; s=n+1;memset(S, 0, sizeof(S));memset(H, -1, sizeof(H));}void DelCol(int c){	// 删除列 for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i], R[L[i]]=R[i];}void ResCol(int c){	// 恢复列 for(int i=U[c]; i!=c; i=U[i])L[R[i]]=R[L[i]]=i;}void AddNode(int r,int c){	// 添加节点 ++S[c], C[++s]=c, X[s]=r;D[s]=D[c], U[D[c]]=s, U[s]=c, D[c]=s;if(H[r]<0) H[r]=L[s]=R[s]=s;	// 行首节点else R[s]=R[H[r]], L[R[H[r]]]=s, L[s]=H[r], R[H[r]]=s;}int f(){int ret=0;memset(vis, 0, sizeof(vis));for(int i=R[0]; i; i=R[i])if(!vis[i]){ret++; vis[i]=1;for(int j=D[i]; j!=i; j=D[j])for(int k=R[j]; k!=j; k=R[k])vis[C[k]]=1;    }return ret;}void dfs(int d){	// 深度,深搜遍历 if(d+f() >= ansd) return;if(!R[0]){if(d<ansd) ansd=d;return;}int c=R[0];for(int i=R[0]; i; i=R[i]) if(S[i]<S[c]) c=i;for(int i=D[c]; i!=c; i=D[i]){DelCol(i); A[d]=X[i];for(int j=R[i]; j!=i; j=R[j]) DelCol(j);dfs(d+1);for(int j=L[i]; j!=i; j=L[j]) ResCol(j);ResCol(i);}}
} dlx; double eps = 1e-8;
struct point{double x, y;
} ci[60], sta[60];double dist(point a, point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}int main(){int n, m, k, cas;scanf("%d", &cas);while(cas--) {scanf("%d%d%d", &n, &m, &k);for(int i=0; i<n; i++) 	scanf("%lf%lf", &ci[i].x, &ci[i].y);for(int i=0; i<m; i++) 	scanf("%lf%lf", &sta[i].x, &sta[i].y);double l=0, r=2000, mid;while(r-l>=eps){dlx.init(n);mid = (l+r)/2;for(int i=0; i<m; i++)for(int j=0; j<n; j++)if(dist(ci[j],sta[i])<=mid)dlx.AddNode(i+1,j+1);dlx.ansd = 1<<30;dlx.dfs(0);if(dlx.ansd<=k) r = mid-eps;else l = mid+eps;}printf("%.6f\n", l);}
}

这篇关于HDU-2295___Radar —— 二分 + DLX重复覆盖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下:需要在

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行

Spring Boot 整合 ShedLock 处理定时任务重复执行的问题小结

《SpringBoot整合ShedLock处理定时任务重复执行的问题小结》ShedLock是解决分布式系统中定时任务重复执行问题的Java库,通过在数据库中加锁,确保只有一个节点在指定时间执行... 目录前言什么是 ShedLock?ShedLock 的工作原理:定时任务重复执行China编程的问题使用 Shed

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,

vue解决子组件样式覆盖问题scoped deep

《vue解决子组件样式覆盖问题scopeddeep》文章主要介绍了在Vue项目中处理全局样式和局部样式的方法,包括使用scoped属性和深度选择器(/deep/)来覆盖子组件的样式,作者建议所有组件... 目录前言scoped分析deep分析使用总结所有组件必须加scoped父组件覆盖子组件使用deep前言

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》:本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一:使用 left join + 子查询删除重复数据(推荐)方法二:创建临时表(需分多步执行,逻辑清晰,但会

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ