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 及通用技术内容,本期分享的全部是英文材料。(标题取自其中两则分享,不代表全部内容都是该主题,特此声明。…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
