【图论】差分约束
一.情景导入
x1-x0<=9 ; x2-x0<=14 ; x3-x0<=15 ; x2-x1<=10 ; x3-x2<=9;
求x3-x0的最大值;
二.数学解法
联立式子2和5,可得x3-x0<=23;但式子3可得x3-x0<=15。所以最大值为15;
三.图论
但式子多了我们就不好解了,或者说在计算机中怎么解呢?
我们可以想到,不妨把式子转为图的形式。我们令x0-->x1的边表示为x1-x0<=边权值。
则以上式子可以画图为:

这边,x3-x0可以为:(即x3-x0<=15)

也可以为:(即x3-x0<=28)

还可以为 :(即x3-x0<=25)

所以我们取最短路径即可!
四.差分约束
这个即是差分约束的模型


注意:
当出现负环的情况,我们可知,式子是无解的!(所以要用spfa算法判断负环)
当要求的两个点没有联通时,可知这两个式子没有约束!所有解都有可能!
五.例题:
3169 -- 布局 (poj.org)

样例输入:
4 2 1 1 3 10 2 4 20 2 3 3样例输出:
27
六.参考代码
/*
4 2 1
1 3 10
2 4 20
2 3 327
*/#include<bits/stdc++.h>
#define maxn 20005
#define maxm 1001
#define inf 0x7fffffff
using namespace std;
int cnt=0;
struct Edge{int u,v,w,next;
}edge[maxn];
int head[maxm];
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int n,x,y;
bool vis[maxm];
int in[maxm],dis[maxn]; //判断负环
//基础,不会的话看我以前的博客
int spfa(int x){queue<int> q;for(int i=1;i<=n;i++){dis[i]=inf;}dis[x]=0;in[x]++;q.push(x);while(!q.empty()){int u=q.front(); q.pop();vis[u]=0;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v,w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=1;q.push(v);in[v]++;if(in[v]>n) return -1; //负环 }}} }if(dis[n]==inf) return -2; //无限制return dis[n];
}
int main(){cin>>n>>x>>y;int u,v,w;for(int i=1;i<=x;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);}for(int i=1;i<=y;i++){scanf("%d%d%d",&u,&v,&w);add(v,u,-w);}//是站成一条直线 for(int i=1;i<n;i++){add(i+1,i,-1);}cout<<spfa(1); return 0;
}
相关文章:
【图论】差分约束
一.情景导入 x1-x0<9 ; x2-x0<14 ; x3-x0<15 ; x2-x1<10 ; x3-x2<9; 求x3-x0的最大值; 二.数学解法 联立式子2和5,可得x3-x0<23;但式子3可得x3-x0<15。所以最大值为15; 三.图论 但式子多了我们就不好解了࿰…...
13 springboot项目——准备数据和dao类
13.1 静态资源下载 https://download.csdn.net/download/no996yes885/88151513 13.2 静态资源位置 css样式文件放在static的css目录下;static的img下放图片;template目录下放其余的html文件。 13.3 创建两个实体类 导入依赖:lombok <!…...
Java 基础进阶总结(一)反射机制学习总结
文章目录 一、初识反射机制1.1 反射机制概述1.2 反射机制概念1.3 Java反射机制提供的功能1.4 反射机制的优点和缺点 二、反射机制相关的 API 一、初识反射机制 1.1 反射机制概述 JAVA 语言是一门静态语言,对象的各种信息在程序运行时便已经确认下来了,内…...
ERROR: transport error 202: gethostbyname: unknown host报错解决方案
Java 9 syntax for remote debugger: -agentlib:jdwptransportdt_socket,servery,suspendn,address*:5005Java 8 不适用 *:port,应该使用: -agentlib:jdwptransportdt_socket,servery,suspendn,address5005参考 https://stackoverflow.com/questions/50344957/ja…...
PyTorch高级教程:自定义模型、数据加载及设备间数据移动
在深入理解了PyTorch的核心组件之后,我们将进一步学习一些高级主题,包括如何自定义模型、加载自定义数据集,以及如何在设备(例如CPU和GPU)之间移动数据。 一、自定义模型 虽然PyTorch提供了许多预构建的模型层&#…...
JavaEE——SpringMVC中的常用注解
目录 1、RestController (1)、Controller (2)、ResponseBody 2、RequestMappping (1)、定义 (2)、使用 【1】、修饰方法 【2】、修饰类 【3】、指定方法类型 【4】、简化版…...
【严重】Metabase 基于H2引擎的远程代码执行漏洞
漏洞描述 Metabase 是一个开源的数据分析和可视化工具。 由于 CVE-2023-38646 的补丁(从H2 JDBC连接字符串中删除INIT脚本以防止命令注入)修复不完全,Metabase 仍受到命令注入的影响。攻击者可使用 H2 作为数据库引擎,通过 /api/setup/validate 端点发…...
0基础学习VR全景平台篇 第75篇:多现场
多现场是指将多台设备的直播画面整合到一个直播活动链接里面,让用户自行选择切换要看哪个直播画面的功能。既可以是同一个活动的不同角度直播,也可以是异地的直播。多现场不需要导播台,并且可以同时支持平面直播和VR直播的混合切换。多现场仅…...
html:去除input/textarea标签的拼写检查
默认情况下,textarea 会启动拼写和语法检查,表现效果就是单词拼写错误会出现红色下划线提示 <textarea></textarea>效果 有时,我们并不需要拼写检查,可以通过配置属性spellcheck"false" 去除拼写和语法检…...
自然语言处理从入门到应用——LangChain:提示(Prompts)-[提示模板:创建自定义提示模板和含有Few-Shot示例的提示模板]
分类目录:《自然语言处理从入门到应用》总目录 创建自定义提示模板 假设我们希望LLM根据函数名称生成该函数的英文语言解释。为了实现这个任务,我们将创建一个自定义的提示模板,以函数名称作为输入,并格式化提示模板以提供函数的…...
d3dx9_30.dll如何修复,分享几种一键修复方法
d3dx9_30.dll是DirectX 的一个动态链接库文件,它包含了一些用于图形和游戏的函数和资源。在了解d3dx9_30.dll的解决方法和丢失原因之前,我们先来了解一下DirectX。DirectX是一套由微软开发的多媒体和游戏编程接口(API)集合。它提供…...
6.8 稀疏数组
6.8 稀疏数组 稀疏数组是一种数据结构,在程序中数据结构的思想,是非常重要的。例如 需求:编写五子棋游戏中,有存盘退出和续上盘的功能。分析问题:因为该二维数组的很多值是默认值0,因此记录了很多没有意义…...
ROS版本的ORB-SLAM3用RealSense D455相机实时运行测试
配置环境 1. C11 检查G版本,查看是否支持C11 一般g版本大于4.7即可 g -v 2. Pangolon 地址:https://github.com/stevenlovegrove/Pangolin 先安装OpenGL,Glew ### 编译orb-slam3发现pangolin编译错误排查的环境问题 sudo apt install p…...
Vue中对对象内容调用的Demo
目录 1.对象作为数据: 2.对象数组 在Vue中,你可以通过对象的键来调用对象中的各个部分的内容。下面是一些使用Vue调用对象各部分内容的示例: 1.对象作为数据: 如果你在Vue实例的数据中有一个对象,你可以使用点语法来…...
语音识别 — 特征提取 MFCC 和 PLP
一、说明 语音识别是一种技术,通过计算机和软件系统,将人们的口头语言转换为计算机可读的文本或命令。它使用语音信号处理算法来识别和理解人类语言,并将其转换为计算机可处理的格式。语音识别技术被广泛应用于许多领域,如语音助手…...
BES 平台 SDK之按键的配置
本文章是基于BES2700 芯片,其他BESxxx 芯片可做参考,如有不当之处,欢迎评论区留言指出。仅供参考学习用! BES 平台 SDK之LED的配置_谢文浩的博客-CSDN博客 关于系统LED简介可参考上一篇文章。链接如上所示! 一&…...
【Golang系统开发】搜索引擎(1) 如何快速判断网页是否已经被爬取
文章目录 1. 写在前面2. 数组存储3. 位图存储3.1 位图简介3.2 链表法3.3 开放寻址法 1. 写在前面 在实际工作中,我们经常需要判断一个对象是否存在,比如判断用户注册登陆时候,需要判断用户是否存在,再比如搜索引擎中的爬虫&#x…...
记录--一个好用的轮子 turn.js 实现仿真翻书的效果
这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助 国际惯例,官网链接 官网传送门 Github地址 github上有几个demos例子,介绍了基础用法。 我参考官网的例子,写了一个demo示例 安装 turn.js 依赖 jquery 库࿰…...
《Spring Boot源码解读与原理分析》书籍推荐
Spring Boot是目前Java EE开发中颇受欢迎的框架之一。依托于底层Spring Framework的基础支撑,以及完善强大的特性设计,Spring Boot已成为业界流行的应用和微服务开发基础框架。 《Spring Boot源码解读与原理分析》共14章,分为4个部分。第一部…...
C++ 什么时候使用 vector、list、以及 deque?
如果需要高效地快速访问(随即存取),并且不在乎插入和删除的效率,使用 vector 如果需要大量的插入和删除,而且不关心快速访问 (随即存取) ,使用 list 如果需要快速访问 (随即存取) ,并且关心两端数据插入和删除&#…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
