HDU Go Running(最小点覆盖 + 网络流优化)


题目大意:有一条无限长跑道,每个人可以规定自己跑步的方向,起点,跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告,每个报告给出了某人在某一时候所在的位置,问跑步的最少可能人数是多少。

思路:建立一个横坐标为 t ,纵坐标为 x 的二维坐标系。从输入得到的每一对 t , x 都是坐标系上的一个点。每个人可以从东往西跑,也可以从西往东跑,所以相对应的在这个坐标系上每个点的斜率可以是 1 ,也可以是 -1 。根据这两种斜率可以得到相对应在 x 轴上的截距,然后就能够建立二分图。网络流建图就是在二分图的基础上,加上一个源点和一个汇点,然后分别建立源点和汇点到二分图的边。(网络流和二分图建图的区别是二分图两边建边的时候,可以有重复的编号,例如:1 -> 1 。但是,网络流建图的时候两个相连的点不能是重复的,例如:1 -> 2 。所以在网络流建边的时候每个编号都要保证不相同!!!)。
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pii pair<int,int>
const int N=3e5+5,M=6e5+5;
struct Edge{int to,w,next;
}edge[M];
int head[N],d[N],cur[N],l[N],r[N];
int n,m,s,t,cnt,k;
void add(int u,int v,int w){edge[cnt]={v,w,head[u]};head[u]=cnt++;
}
bool bfs(){memset(d,0,sizeof d);queue<int> q;q.push(s);d[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(d[v]==0 && edge[i].w){d[v]=d[u]+1;q.push(v);if(v==t) return true;}}}return false;
}
int dfs(int u,int flow){if(u==t) return flow;int sum=0;for(int i=cur[u];i!=-1;i=edge[i].next){cur[u]=i;int v=edge[i].to;if(d[v]==d[u]+1 && edge[i].w){int f=dfs(v,min(flow,edge[i].w));edge[i].w-=f;edge[i^1].w+=f;sum+=f;flow-=f;if(!flow) break;}}if(!sum) d[u]=0;return sum;
}
int dinic(){int ans=0;while(bfs()){memcpy(cur,head,sizeof head);ans+=dfs(s,1e18);}return ans;
}
signed main(){IOSint _;cin >> _;while(_--){cnt=0;memset(head,-1,sizeof head);cin >> n;unordered_map<int,int> lx,rx;//给编号去重 int a=0,b=0;//记录两种斜率直线对于 y 轴截距的编号 for(int i=1;i<=n;i++){int u,v;//u,v 对应 t,xcin >> u >> v;if(!lx.count(v-u)) lx[v-u]=++a;if(!rx.count(v+u)) rx[v+u]=++b;l[i]=lx[v-u],r[i]=rx[v+u];//记录每个点对应其两个截距的编号}for(int i=1;i<=n;i++){//二分图建边 add(l[i],r[i]+a,1);//加 a 是因为不能有重复编号add(r[i]+a,l[i],0);}s=0,t=a+b+1;//添加源点和汇点for(int i=1;i<=a;i++){//源点与二分图一边相连 add(s,i,1);add(i,s,0);}for(int i=1;i<=b;i++){//汇点与二分图另一边相连 add(i+a,t,1);add(t,i+a,0);}cout << dinic() << endl;//套用网络流模板 }return 0;
}
//b=x-t lx
//b=x+t rx
相关文章:
HDU Go Running(最小点覆盖 + 网络流优化)
题目大意:有一条无限长跑道,每个人可以规定自己跑步的方向,起点,跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告,每个报告给出了某人在某一时候所在的位置,问跑步的最少可能人数…...
C++设计模式-中介者模式
动机(Motivation) 多个对象相互关联的情况,对象之间常常会维持一种复杂的引用关系,如果遇到一些需求的更改,这种直接的引用关系将面临不断的变化。在这种情况下,可以使用一种”中介对象“来管理对象间的关联关系,避免…...
文件上传与下载服务 | Flask 实战
之前介绍了 droppy 文件共享服务的搭建。但在一些场景中,我们需要在命令行或在 Python 代码中,临时上传和下载文件。这时可以用一个更简单的策略:使用 flask 编写一个临时的 API。 服务端配置 以下是一个简单的 Flask 应用程序代码示例&…...
MySQL 中的排序:索引排序与文件排序
文章目录 MySQL 中的排序:索引排序与文件排序全解析一、引言二、索引排序(一)原理(二)示例 三、文件排序(一)单路排序(二)双路排序(三)归并排序 四…...
深入理解React Hooks:使用useState和useEffect
引言 React Hooks是React 16.8引入的一项强大功能,它使函数组件能够使用状态和其他React特性。本文将深入探讨两个最常用的Hooks:useState和useEffect,并通过实际代码示例展示它们的使用方法。 1. 什么是React Hooks? React Ho…...
AWS codebuild + jenkins + github 实践CI/CD
前文 本文使用 Jenkins 结合 CodeBuild, CodeDeploy 实现 Serverless 的 CI/CD 工作流,用于自动化发布已经部署 lambda 函数。 在 AWS 海外区,CI/CD 工作流可以用 codepipeline 这项产品来方便的实现, CICD 基本概念 持续集成( Continuous…...
Android PMS(Package Manager Service)源码介绍
文章目录 前言一、PMS 启动流程二、APK 安装流程三、APK 卸载流程四、权限管理静态权限动态权限 五、 数据存储与一致性六、 PMS 的安全性策略1、权限检查2、签名认证3、动态权限管理4、应用安装验证5、保护系统目录 七、PMS 调试方法总结 前言 PackageManagerService…...
运维面试整理总结
面试题可以参考:面试题总结 查看系统相关信息 查看系统登陆成功与失败记录 成功:last失败:lastb 查看二进制文件 hexdump查看进程端口或连接 netstat -nltp ss -nltp补充:pidof与lsof命令 pidof [进程名] #根据 进程名 查询进程id ls…...
图数据库 Cypher语言
图数据库 属性图 属性图(Property Graph)概述 属性图是一种广泛用于建模关系数据的图数据结构,它将**顶点(节点)和边(关系)**进行结构化存储,并为它们附加属性以提供丰富的语义信…...
阿里云oss转发上线-实现不出网钓鱼
本地实现阿里云oss转发上线,全部代码在文末,代码存在冗余 实战环境 被钓鱼机器不出网只可访问内部网络包含集团oss 实战思路 若将我们的shellcode文件上传到集团oss上仍无法上线,那么就利用oss做中转使用本地转发进行上线,先发送…...
Spring Boot 3.4.0 发行:革新与突破的里程碑
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/literature?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,…...
【网络安全】
黑客入侵 什么是黑客入侵? “黑客”是一个外来词,是英语单词hacker的中文音译。最初,“黑客”只是一个褒义词,指的是那些尽力挖掘计算机程序最大潜力的点脑精英,他们讨论软件黑客的技巧和态度,以及共享文化…...
在SQLyog中导入和导出数据库
导入 假如我要导入一个xxx.sql,我就先创建一个叫做xxx的数据库。 然后右键点击导入、执行SQL脚本 选择要导入的数据库文件的位置,点击执行即可 注意: 导入之后记得刷新一下导出 选择你要导出的数据库 右键选择:备份/导出、…...
RabbitMQ简单应用
概念 RabbitMQ 是一种流行的开源消息代理(Message Broker)软件,它实现了高级消息队列协议(AMQP - Advanced Message Queuing Protocol)。RabbitMQ 通过高效的消息传递机制,主要应用于分布式系统中解耦应用…...
使用LUKS对Linux磁盘进行加密
前言 本实验用于日常学习用,如需对存有重要数据的磁盘进行操作,请做好数据备份工作。 此实验只是使用LUKS工具的冰山一角,后续还会有更多功能等待探索。 LUKS(Linux Unified Key Setup)是Linux系统中用于磁盘加密的一…...
戴尔电脑安装centos7系统遇到的问题
1,找不到启动盘(Operation System Loader signature found in SecureBoot exclusion database(‘dbx’).All bootable devices failed secure Boot Verification) 关闭 Secure Boot(推荐): 进入 BIOS/UEFI…...
3.4.SynchronousMethodHandler组件之ResponseHandler
前言 feign发送完请求后, 拿到返回结果, 那么这个返回结果肯定是需要经过框架进一步处理然后再返回到调用者的, 其中ResponseHandler就是用来处理这个返回结果的, 这也是符合正常思维的处理方式, 例如springmvc部分在调用在controller端点前后都会增加扩展点。 从图中可以看得…...
Linux 下进程的状态
操作系统中常见进程状态 在操作系统中有六种常见进程状态: 新建状态: 进程正在被创建. 此时操作系统会为进程分配资源, 如: 内存空间等, 进行初始化就绪状态: 进程已经准备好运行了, 只需要等待被调度, 获取 CPU 资源就可以执行了, 操作系统中可能同时存在多个进程处于就绪状…...
【计算机网络】核心部分复习
目录 交换机 v.s. 路由器OSI七层更实用的TCP/IP四层TCPUDP 交换机 v.s. 路由器 交换机-MAC地址 链接设备和设备 路由器- IP地址 链接局域网和局域网 OSI七层 物理层:传输设备。原始电信号比特流。数据链路层:代表是交换机。物理地址寻址,交…...
Spring Boot开发实战:从入门到构建高效应用
Spring Boot 是 Java 开发者构建微服务、Web 应用和后端服务的首选框架之一。其凭借开箱即用的特性、大量的自动化配置和灵活的扩展性,极大简化了开发流程。本文将以实战为核心,从基础到高级,全面探讨 Spring Boot 的应用开发。 一、Spring B…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
