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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479854.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

28.UE5实现对话系统

目录 1.对话结构的设计&#xff08;重点&#xff09; 2.NPC对话接口的实现 2.1创建类型为pawn的蓝图 2.2创建对话接口 3.对话组件的创建 4.对话的UI设计 4.1UI_对话内容 4.2UI_对话选项 4.3UI_对话选项框 5.对话组件的逻辑实现 通过组件蓝图&#xff0c;也就是下图中的…

Reachy 2,专为AI与机器人实验室打造的卓越开源双臂移动操作平台!

近期&#xff0c;花粉机器人&#xff08;POLLEN ROBOTICS&#xff09;隆重推出Reachy 2仿生机器人——下一代开源操作平台&#xff0c;为AI与机器人实验室带来理想的双臂移动操作科研平台&#xff01; Reachy 2的仿生性&#xff1a; 》拥有两个基于Maxon无刷电机的仿生7自由度…

python的openpyxl库设置表格样式:字体/边框/对齐/颜色等

学习目录 1. 安装和使用openpyxl库设置表格样式 2 设置字体font 3 设置边框 4 设置对齐方式 5 设置单元格数据格式 6 设置行高和列宽 7 填充单元格颜色 附录-关于颜色说明 本章节主要介绍如何使用openpyxl库设置表格中的一些样式&#xff0c;比如字体&#xff0c;边框…

Git旧文件覆盖引发思考

一天&#xff0c;我的同事过来找到我&#xff0c;和我讲&#xff1a;张叫兽&#xff0c;大事不好&#xff0c;我的文件被人覆盖了。git是真的不好用啊 git不好用&#xff1f;文件被覆盖&#xff1b;瞬间我似乎知道了什么&#xff0c;让我想到了某位男明星的语法&#xff1a;他…

QSqlTableModel的使用

实例功能 这边使用一个实例显示数据库 demodb 中 employee 数据表的内容&#xff0c;实现编辑、插入、删除的操作&#xff0c;实现数据的排序和记录过滤&#xff0c;还实现 BLOB 类型字段 Photo 中存储照片的显示、导入等操作&#xff0c;运行界面如下图&#xff1a; 在上图中…

什么是代理,nodenginx前端代理详解

一. 什么是代理&#xff1f; 代理就是通过一个特殊的网络服务去访问另一网络服务的一种间接访问方式。像我们不能直接访问国外的网站&#xff0c;只能使用VPN&#xff0c;就是使用了代理 二. 前端为什么要用代理&#xff1f; 首先明确以下两个概念 &#xff08;1&#xff09…

java脚手架系列16-AI大模型集成

之所以想写这一系列&#xff0c;是因为之前工作过程中有几次项目是从零开始搭建的&#xff0c;而且项目涉及的内容还不少。在这过程中&#xff0c;遇到了很多棘手的非业务问题&#xff0c;在不断实践过程中慢慢积累出一些基本的实践经验&#xff0c;认为这些与业务无关的基本的…

网络安全中的数据科学如何重新定义安全实践?

组织每天处理大量数据&#xff0c;这些数据由各个团队和部门管理。这使得全面了解潜在威胁变得非常困难&#xff0c;常常导致疏忽。以前&#xff0c;公司依靠 FUD 方法&#xff08;恐惧、不确定性和怀疑&#xff09;来识别潜在攻击。然而&#xff0c;将数据科学集成到网络安全中…

【算法day1】数组:双指针算法

题目引用 这里以 1、LeetCode704.二分查找 2、LeetCode27.移除元素 3、LeetCode977.有序数组的平方 这三道题举例来说明数组中双指针的妙用。 1、二分查找 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜…

open-instruct框架使用记录:只使用huggingface数据集的小部分进行训练,如何修改dataset_info.json文件

open-instruct框架 这篇笔记主要记录以下问题&#xff1a;只使用huggingface下载的数据集中的一小部分数据进行数据训练。而且我不想修改open-instruct的加载数据集的代码&#xff0c;以及脚本中的--dataset_mixer_list参数的指定等。下面是我的思路历程。 if args.dataset_na…

Jenkins升级到最新版本后无法启动

1. 场景还原 最近在web界面将jenkins升级到最新版本后&#xff0c;后台无法启动jenkins服务&#xff0c;服务状态如下&#xff1a; 运行jenkins命令提示invalid Java version jenkins --version jenkins: invalid Java version: java version "1.8.0_202" Java(TM)…

DRM(数字权限管理技术)防截屏录屏----ffmpeg安装

提示&#xff1a;ffmpeg安装 文章目录 [TOC](文章目录) 前言一、下载二、配置环境变量三、运行ffmpeg四、文档总结 前言 FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的…

Unity版本使用情况统计(更新至2024年11月)

UWA发布&#xff5c;本期UWA发布的内容是第十五期Unity版本使用统计&#xff0c;统计周期为2024年5月至2024年11月&#xff0c;数据来源于UWA网站&#xff08;www.uwa4d.com&#xff09;性能诊断提测的项目。希望给Unity开发者提供相关的行业趋势作为参考。 2024年5月 - 2024年…

Spring Aop 中对JoinPoint的理解

以下是源码中对 JoinPoint 的描述 A runtime joinpoint is an event that occurs on a static joinpoint (i.e. a location in a program). For instance, an invocation is the runtime joinpoint on a method (static joinpoint). The static part of a given joinpoint can…

C中指针在64位操作系统下为什么是4而不是8

好久没写C了&#xff0c;今天用VScode想写个Demo&#xff0c;翻了下指针资料&#xff0c;想打印下指针大小&#xff0c;发现是4&#xff0c;但是理论上64位系统不应该是8么&#xff1f; 结论就是我编的是32位程序&#xff0c;编译器按照32位编译的。 用vscode的C 插件编译运行…

使用 pycharm 新建不使用 python 虚拟环境( venv、conda )的工程

有时候我们发现一个好玩的 demo&#xff0c;想赶快在电脑上 pip install 一下跑起来&#xff0c;发现因为 python 的 venv、conda 环境还挺费劲的&#xff0c;因为随着时间的发展&#xff0c;之前记得很清楚的 venv、conda 的用法&#xff0c;不经常使用&#xff0c;半天跑不起…

鸿蒙主流路由详解

鸿蒙主流路由详解 Navigation Navigation更适合于一次开发,多端部署,也是官方主流推荐的一种路由控制方式,但是,使用起来入侵耦合度高,所以,一般会使用HMRouter,这也是官方主流推荐的路由 Navigation官网地址 个人源码地址 路由跳转 第一步-定义路由栈 Provide(PageInfo) pag…

Flink Sink的使用

经过一系列Transformation转换操作后&#xff0c;最后一定要调用Sink操作&#xff0c;才会形成一个完整的DataFlow拓扑。只有调用了Sink操作&#xff0c;才会产生最终的计算结果&#xff0c;这些数据可以写入到的文件、输出到指定的网络端口、消息中间件、外部的文件系统或者是…

鸿蒙本地模拟器 模拟TCP服务端的过程

鸿蒙模拟器模拟TCP服务端的过程涉及几个关键步骤&#xff0c;主要包括创建TCPSocketServer实例、绑定IP地址和端口、监听连接请求、接收和发送数据以及处理连接事件。以下是详细的模拟过程&#xff1a; **1.创建TCPSocketServer实例&#xff1a;**首先&#xff0c;需要导入鸿蒙…

【VUE3】新版Vue3+ElementPlus全家桶开发视频项目实战

VUE 介绍 Vue (发音为 /vjuː/,类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建,并提供了一套声明式的、组件化的编程模型,帮助你高效地开发用户界面。 Vue.js是一个MVVM(Model - View - ViewModel)的SPA框架。 Model:数…