P5960 【模板】差分约束算法
【模板】差分约束算法
题目描述
给出一组包含 m m m 个不等式,有 n n n 个未知数的形如:
{ x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩ ⎨ ⎧xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym
的不等式组,求任意一组满足这个不等式组的解。
输入格式
第一行为两个正整数 n , m n,m n,m,代表未知数的数量和不等式的数量。
接下来 m m m 行,每行包含三个整数 c , c ′ , y c,c',y c,c′,y,代表一个不等式 x c − x c ′ ≤ y x_c-x_{c'}\leq y xc−xc′≤y。
输出格式
一行, n n n 个数,表示 x 1 , x 2 ⋯ x n x_1 , x_2 \cdots x_n x1,x2⋯xn 的一组可行解,如果有多组解,请输出任意一组,无解请输出 NO。
样例 #1
样例输入 #1
3 3
1 2 3
2 3 -2
1 3 1
样例输出 #1
5 3 5
提示
样例解释
{ x 1 − x 2 ≤ 3 x 2 − x 3 ≤ − 2 x 1 − x 3 ≤ 1 \begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases} ⎩ ⎨ ⎧x1−x2≤3x2−x3≤−2x1−x3≤1
一种可行的方法是 x 1 = 5 , x 2 = 3 , x 3 = 5 x_1 = 5, x_2 = 3, x_3 = 5 x1=5,x2=3,x3=5。
{ 5 − 3 = 2 ≤ 3 3 − 5 = − 2 ≤ − 2 5 − 5 = 0 ≤ 1 \begin{cases}5-3 = 2\leq 3 \\ 3 - 5 = -2 \leq -2 \\ 5 - 5 = 0\leq 1 \end{cases} ⎩ ⎨ ⎧5−3=2≤33−5=−2≤−25−5=0≤1
数据范围
对于 100 % 100\% 100% 的数据, 1 ≤ n , m ≤ 5 × 1 0 3 1\leq n,m \leq 5\times 10^3 1≤n,m≤5×103, − 1 0 4 ≤ y ≤ 1 0 4 -10^4\leq y\leq 10^4 −104≤y≤104, 1 ≤ c , c ′ ≤ n 1\leq c,c'\leq n 1≤c,c′≤n, c ≠ c ′ c \neq c' c=c′。
评分策略
你的答案符合该不等式组即可得分,请确保你的答案中的数据在 int 范围内。
如果并没有答案,而你的程序给出了答案,SPJ 会给出 There is no answer, but you gave it,结果为 WA;
如果并没有答案,而你的程序输出了 NO,SPJ 会给出 No answer,结果为 AC;
如果存在答案,而你的答案错误,SPJ 会给出 Wrong answer,结果为 WA;
如果存在答案,且你的答案正确,SPJ 会给出 The answer is correct,结果为 AC。
差分约束模板
我们知道在SPFA中,在单源最短路问题中,如果存在一条 𝑖 → 𝑗 长为 𝑤 的边,在计算1
号点到每个点的最短路后,一定有 𝑑𝑖𝑠[𝑖] + 𝑤 ≥ 𝑑𝑖𝑠[𝑗]。
x i + c ≥ x j x_i+c \ge x_j xi+c≥xj 与其相同
所以若存在 x i + c ≥ x j x_i+c \ge x_j xi+c≥xj,使用图论便是:连边(i,j,c)
代码
#include<bits/stdc++.h>
using namespace std;
const int M=1e4;
int dis[M],cnt[M];
bool inQueue[M];
queue<int> Q;
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
#define for_(i,a,b) for(int i=(a);i>=(b);i--)
#define _rep(i,a,b) for(int i=(a);i<(b);i++)
vector<pair<int, int> > edges[M];
void add(int u,int v,int w){edges[u].emplace_back(v, w);
}
bool spfa(int s,int n){memset(dis, 0x3f, sizeof(dis));dis[s] = 0;Q.push(s);inQueue[s] = true;while (!Q.empty()) {int x = Q.front();Q.pop();inQueue[x] = false;for (auto edge: edges[x]) {if (dis[edge.first] <= dis[x] + edge.second)continue;dis[edge.first] = dis[x] + edge.second;if (!inQueue[edge.first]) {Q.push(edge.first);inQueue[edge.first] = true;cnt[edge.first]++;if (cnt[edge.first]>1+n) return false;}}}return true;
}
int main(){int n,m;cin>>n>>m;_for(i,1,n) add(0,i,0);_for(i,1,m){int u,v,w;cin>>v>>u>>w;add(u,v,w);}if (!spfa(0,n)) {cout<<"NO";return 0;}_for(i,1,n) cout<<dis[i]<<' ';return 0;
}
分析
spfa模板+上面的分析,这里说下存图:
vector<pair<int, int> > edges[M];
就是 vector<pair<v,w> >edges[u];
相关文章:
P5960 【模板】差分约束算法
【模板】差分约束算法 题目描述 给出一组包含 m m m 个不等式,有 n n n 个未知数的形如: { x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\…...
VSCode---通过ctrl+鼠标滚动改变字体大小
打开设置然后在右边输editor.mouseWheelZoo勾选即可实现鼠标滚动改变字体大小 4.这种设置的字体大小是固定的...
视频监控汇聚平台EasyCVR视频分享页面WebRTC流地址播放不了是什么原因?
开源EasyDarwin视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理,在视频监控播放上,TSINGSEE青犀视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放,可同时播放多…...
Libevent开源库的介绍与应用
libeventhttps://libevent.org/ 一、初识 1、libevent介绍 Libevent 是一个用C语言编写的、轻量级的开源高性能事件通知库,主要有以下几个亮点:事件驱动( event-driven),高性能;轻量级,专注于网络ÿ…...
【LNMP】LNMP
LNMP:是目前成熟的企业网站的应用模式之一,指的是一套协同工作的系统和相关软件;能够提供静态页面服务,也可以提供动态web服务 L Linux系统,操作系统N Nginx网站服务,前端,提供前端的静态…...
uniapp自定义头部导航栏
有时我们需要一些特殊的头部导航栏页面,取消传统的导航栏,来增加页面的美观度。 下面我就教大家如何配置: 一、效果图 二、实现 首先在uniapp中打开pages.json配置文件,在单个路由配置style里面设置导航栏样式nav…...
Django实现音乐网站 ⑹
使用Python Django框架制作一个音乐网站, 本篇主要是在添加编辑过程中对后台歌手功能优化及表模型名称修改、模型继承内容。 目录 表模型名称修改 模型继承 创建抽象基类 其他模型继承 更新表结构 歌手新增、编辑优化 表字段名称修改 隐藏单曲数和专辑数 姓…...
dubbo-helloworld示例
1、工程架构 2、创建模块 (1)创建父工程,引入公共依赖 pom.xml依赖 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></depende…...
电脑ADB连接手机的方式通过网络无法adb连接手机的问题(已解决)
首先电脑要下载adb工具,将压缩包解压到C盘:https://download.csdn.net/download/qq_43445867/87975072 1、使用USB线连接 打开手机USB调试;PC端安装手机USB驱动。 1.打开DOS命令窗口,进入adb文件夹,输入adb.exe devices回车列出设…...
79 | Python数据分析篇 —— Pandas中groupby聚合操作和透视表基础
Pandas是Python中最常用的数据处理库之一,它提供了高效的数据结构和数据分析工具。在进行数据分析和机器学习等领域的工作时,Pandas是必不可少的库之一。本文将介绍Pandas中的groupby聚合操作和透视表,包括groupby操作、透视表的基础知识、练习题和答案。 文章目录 Pandas中…...
iOS 搭建组件化私有库
一、创建私有库索引 步骤1是在没有索引库的情况下或者是新增索引的时候才需要用到(创建基础组件库) 首先在码云上建立一个私有库索引,起名为SYComponentSpec 二、本地添加私有库索引 添加私有库索引 pod repo add SYComponentSpec https:/…...
迅为全国产龙芯3A5000电脑运行统信UOS、银河麒麟、loongnix系统
iTOP-3A5000开发板采用全国产龙芯3A5000处理器,基于龙芯自主指令系统 (LoongArch) 的LA464微结构,并进一步提升频率,降低功耗,优化性能。在与龙芯3A4000处理器保持引脚兼容的基础上,频率提升至2.5GHZ,功耗降…...
枫叶时代:打造中国特色的传统文化IP
近年来,取材于传统文化的影视作品在文化产业市场受到前所未有的关注。作为一种兼具辨识度、影响力和流量变现能力的文化符号,影视IP既是文化产业的一个重要环节,也是国家文化软实力的直接体现。优秀的影视IP可以超越文字、语言、民族的障碍&a…...
一条sql语句在mysql中如何执行(查询+更新)
文章目录 一 MySQL 基础架构1.1 MySQL 基本架构1.2 Server 层基本组件介绍1) 连接器2) 查询缓存(MySQL 8.0 版本后移除)3) 分析器4) 优化器5) 执行器 二 语句分析2.1 查询语句2.2 更新语句为什么要用两个日志模块,用一个日志模块不行吗?为什么必须有“两阶段提交”…...
漫画 | TCP/IP之大明邮差
后记: 1973年,卡恩与瑟夫开发出了网络中最核心的两个协议:TCP协议和IP协议,随后为了验证两个协议的可用性,他们做了一个实验,在多个异构网络中进行数据传输,数据包在经过近10万公里的旅程后到达…...
Zookeeper和Nacos的区别
Zookeeper和Nacos的区别 在分布式系统中,注册中心充当着重要角色,是服务发现、客户端负载均衡中不可缺少的一员。注册中心除了能够实现基本的功能外,他的稳定性、可用性和健壮性对整个分布式系统的流畅运行影响重大。zookeeper和nacos可能是…...
O3DE的Pass
Pass介绍 Pass是具有输入和输出的渲染过程。 在最终渲染帧中看到的每个细节都是通过一系列Pass(前一个Pass的输出是下一个Pass的输入)计算出来的。Pass可以生成图像(作为纹理、缓冲区或渲染目标)。每个图像都包含关于场景的特定…...
如何建立含有逻辑删除字段的唯一索引
业务场景 在实际工作当中,遇到一个场景,就是在用户注册时,名字要全局唯一,当然,我们是可以对用户进行删除的,你会怎么去做? 分析 一般来说,我们可以在用户注册请求时,…...
C语言基础知识点一
C语言基础知识点一: 1.数据类型 2.bool类型: 使用bool时时,需要增加<stdbool.h>头文件。 说明:bool 类型只有非零(true)和零(false)两种值。 如: if(-1…...
Python 潮流周刊#14:Lpython 高性能编译器、Python 与 JavaScript 实现互通
△点击上方“Python猫”关注 ,回复“1”领取电子书 你好,我是猫哥。这里每周分享优质的 Python、AI 及通用技术内容,本期分享的全部是英文材料。(标题取自其中两则分享,不代表全部内容都是该主题,特此声明。…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
