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…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
