差分约束算法
差分约束
差分约束系统包含 m m m个涉及 n n n个变量的差额限制条件,这些差额限制条件每个都是形式为 x i − x j ≤ b ∈ [ 1 , m ] x_i-x_j\leq b_{\in[1,m]} xi−xj≤b∈[1,m]的简单线性不等式。
通常我们要求解出一组可行解。
最短路差分约束
如果我们把变量看做节点,如果这里用 d u d_u du表示 d i s S , u dis_{S,u} disS,u,那么从 u u u到 v v v的一条有向边必然满足 d u + w ≥ d v d_u+w\geq d_v du+w≥dv,即:
d v − d u ≤ w d_v-d_u\leq w dv−du≤w
对比:
x v − x u ≤ b i x_v-x_u\leq b_i xv−xu≤bi
因此对于每个限制条件 x v − x u ≤ b i x_v-x_u\leq b_i xv−xu≤bi,我们可以在图上给 u u u到 v v v连接一条边权为 b i b_i bi的有向边。
同时建立一个虚拟源点 S S S,向着每个点连接一个长度为 0 0 0的边。
如果图中不存在负环,那么可以使用单源最短路径算法求出所有的 d u d_u du,则 x i = d i x_i=d_i xi=di就是原问题的一组可行解。如果有负环说明无解。
定理:图中没有负环是差分约束系统有解的充要条件。
充分性显然,因为我们可以构造出一组解。
必要性:
如果图中存在负环,那么说明此差分约束系统无解:
设图中有一个负环, w 1 + w 2 + w 3 < 0 w_1+w_2+w_3<0 w1+w2+w3<0
x 1 + w 1 ≥ x 2 x_1+w_1\geq x_2 x1+w1≥x2
x 1 + w 1 + w 2 ≥ x 2 + w 2 ≥ x 3 x_1+w_1+w_2\geq x_2+w_2\geq x_3 x1+w1+w2≥x2+w2≥x3
x 1 + w 1 + w 2 + w 3 ≥ x 3 + w 3 ≥ x 1 x_1+w_1+w_2+w_3 \geq x_3+w_3\geq x_1 x1+w1+w2+w3≥x3+w3≥x1
x 1 + w 1 + w 2 + w 3 ≥ x 1 x_1+w_1+w_2+w_3 \geq x_1 x1+w1+w2+w3≥x1
这说明 x 1 + 一个负数 ≥ x 1 x_1+一个负数\geq x_1 x1+一个负数≥x1,这是不可能的,因此这个差分约束系统是矛盾的,无解。
QED.
性质
这样建图跑最短路求出的解是具有一定性质的,具体来说是:
- x i ∈ [ 1 , n ] ≤ 0 x_{i\in[1,n]}\leq 0 xi∈[1,n]≤0
- 对于任意差分约束系统的一组解 { x n ′ } \left\{x'_{n}\right\} {xn′}满足 x i ∈ [ 1 , n ] ′ ≤ 0 x'_{i\in[1,n]}\leq 0 xi∈[1,n]′≤0,都有 x i ≥ x i ′ ( i ∈ [ 1 , n ] ) x_i\geq x'_i(i\in[1,n]) xi≥xi′(i∈[1,n]),也就称为最大解
- 对于所有解 x i ∈ [ 1 , n ] ′ ≤ 0 x'_{i\in[1,n]}\leq 0 xi∈[1,n]′≤0,都有 ∑ n i = 1 x i ≥ ∑ n i = 1 x i ′ \underset{i=1}{\overset n\sum}x_i\geq\underset{i=1}{\overset n\sum}x'_i i=1∑nxi≥i=1∑nxi′
证明:
只需证明性质2,性质1、3显然:
首先考虑虚拟源点 S S S的意义,即我们令 x S x_S xS表示一个新量,我们连零边表示: x i ∈ [ 1 , n ] − x S ≤ 0 x_{i\in[1,n]}-x_S\leq 0 xi∈[1,n]−xS≤0。
然后我们在跑最短路时强制 x S = d S = 0 x_S=d_S=0 xS=dS=0,因此我们连零边实际上限制了: x i ∈ [ 1 , n ] ≤ 0 x_{i\in[1,n]}\leq 0 xi∈[1,n]≤0
接下来考虑:
对于 x i = d i x_i=d_i xi=di,假设其对应的某条从 S S S到 i i i的最短路径依次经过了点 u 0 = S , u 1 , u 2 , . . . , u k = i u_0=S,u_1,u_2,...,u_k=i u0=S,u1,u2,...,uk=i,则经过的边对应的不等式为:
x u j − x u j − 1 ≤ w j x_{u_j}-x_{u_{j-1}}\leq w_j xuj−xuj−1≤wj
求和得到:
∑ k j = 1 x u j − x u j − 1 ≤ ∑ k j = 1 w j \underset{j=1}{\overset k\sum}x_{u_j}-x_{u_{j-1}}\leq \underset{j=1}{\overset k\sum} w_j j=1∑kxuj−xuj−1≤j=1∑kwj
由于裂项:
x u k − x u 0 ≤ ∑ k j = 1 w j x_{u_k}-x_{u_0}\leq \underset{j=1}{\overset k\sum}w_j xuk−xu0≤j=1∑kwj
由于我们指定了 x S = 0 x_S=0 xS=0,也就是说:
x i ≤ ∑ k j = 1 w j x_i\leq \underset{j=1}{\overset k\sum}w_j xi≤j=1∑kwj
这给出了此差分约束系统中,满足所有变量都 ≤ 0 \leq 0 ≤0的任意一个解中, x i x_i xi的一个上界。
同时我们断言这个上界是可以取到的,并且 x i = d i = ∑ k j = 1 w j x_i=d_{i}=\underset{j=1}{\overset k\sum}w_j xi=di=j=1∑kwj,原因如下,因为刚才经过的边事实上是由 S S S到 i i i的最短路径,根据相关理论,我们有:
d i s S , u j − d i s S , u j − 1 = w j dis_{S,u_j}-dis_{S,u_{j-1}}=w_j disS,uj−disS,uj−1=wj
求和得到:
∑ k j = 1 d i s S , u j − d i s S , u j − 1 = ∑ k j = 1 w j \underset{j=1}{\overset k\sum}dis_{S,u_j}-dis_{S,u_{j-1}}= \underset{j=1}{\overset k\sum} w_j j=1∑kdisS,uj−disS,uj−1=j=1∑kwj
由于裂项:
d i s S , i = ∑ k j = 1 w j dis_{S,i}=\underset{j=1}{\overset k\sum}w_j disS,i=j=1∑kwj
因此我们知道 x i = d i = d i s S , i = ∑ k j = 1 w j x_i=d_i=dis_{S,i}=\underset{j=1}{\overset k\sum}w_j xi=di=disS,i=j=1∑kwj,证明上界可以取到。
QED.
最长路差分约束
如果我们用 d u d_u du表示 S S S到 u u u的最长路,那么对于有向边 ( u , v ) (u,v) (u,v):
d u + w ≤ d v d_u+w\leq d_v du+w≤dv
d u − d v ≤ − w d_u-d_v\leq -w du−dv≤−w
即:
x u − x v ≤ b i x_u-x_v\leq b_i xu−xv≤bi
那么 b i = − w b_i=-w bi=−w,即 w = − b i w=-b_i w=−bi
那么从 u u u向 v v v连接一条长度为 − b i -b_i −bi的有向边。
在从虚拟源点 S S S向着每个点连接一个边权为 0 0 0的有向边。
求出图中的最长路即为差分约束系统的一组解。
同理图中如果存在正环就无解。
性质
这样建图跑最长路求出的解也具有一定性质的,具体来说是:
- x i ∈ [ 1 , n ] ≥ 0 x_{i\in[1,n]}\geq 0 xi∈[1,n]≥0
- 对于任意差分约束系统的一组解 { x n ′ } \left\{x'_{n}\right\} {xn′}满足 x i ∈ [ 1 , n ] ′ ≥ 0 x'_{i\in[1,n]}\geq 0 xi∈[1,n]′≥0,都有 x i ≤ x i ′ ( i ∈ [ 1 , n ] ) x_i\leq x'_i(i\in[1,n]) xi≤xi′(i∈[1,n]),也就称为最小解
- 对于所有解 x i ∈ [ 1 , n ] ′ ≥ 0 x'_{i\in[1,n]}\geq 0 xi∈[1,n]′≥0,都有 ∑ n i = 1 x i ≤ ∑ n i = 1 x i ′ \underset{i=1}{\overset n\sum}x_i\leq\underset{i=1}{\overset n\sum}x'_i i=1∑nxi≤i=1∑nxi′
证明同理。
其他问题
各类限制转化
通常讨论的差分约束问题往往变量为整数,对于一些其他形式的简单线性不等式可以转化为差分约束问题 x − y ≤ b x-y\leq b x−y≤b:
x − y < b ⇒ x − y ≤ b − 1 x-y<b\Rightarrow x-y\leq b-1 x−y<b⇒x−y≤b−1
x − y ≥ b ⇒ y − x ≤ − b x-y\geq b\Rightarrow y-x\leq -b x−y≥b⇒y−x≤−b
x − y > b ⇒ y − x < − b x-y>b\Rightarrow y-x<-b x−y>b⇒y−x<−b
x − y = b ⇒ x − y ≤ b 且 x − y ≥ b x-y=b\Rightarrow x-y\leq b且x-y\geq b x−y=b⇒x−y≤b且x−y≥b(当然如果全是等式限制直接高斯消元更好)
通常差分约束可能涉及对题意进行差分/前缀和转化。
正解/负解
建最短路得出的解一定是非正解,并且是最大解。
建最长路得出的解一定是非负解,并且是最小解。
同时注意到对一组可行解的每个变量都加 k k k之后,这个解仍然是可行解,因此我们可以获得全正/全负解。
后记
于是皆大欢喜。
相关文章:

差分约束算法
差分约束 差分约束系统包含 m m m个涉及 n n n个变量的差额限制条件,这些差额限制条件每个都是形式为 x i − x j ≤ b ∈ [ 1 , m ] x_i-x_j\leq b_{\in[1,m]} xi−xj≤b∈[1,m]的简单线性不等式。 通常我们要求解出一组可行解。 最短路差分约束 如果我们…...

彻底解决vue-video-player播放视频有黑边
需求 最近需要接入海康视频摄像头,然后把视频的画面接入到自己的网站系统中。以前对接过rtsp固定IP的显示视频,这次的不一样,没有了固定IP。海康的解决办法是,摄像头通过配置服务器到萤石云平台,然后购买企业版账号和…...
区域负责人常用的ChatGPT通用提示词模板
区域市场分析:如何分析区域市场的特点、竞争态势和客户需求? 区域销售策略制定:如何制定针对区域市场的销售策略,包括产品定位、价格策略、渠道策略等? 区域销售目标设定:如何设定明确的区域销售目标&…...
Java Spring boot 可變參數,以及弊端
function中 不固定的參數 public boolean sendEmail(String manFrom, String manTo,String manCc, String subject, String... msg); 必須是最後一個參數,傳值時可以多個。 sendEmail(“a.gmail”,"b.gmail","c.gmail","subject",…...
机器视觉系统选型-线阵工业相机选型
线阵相机特点: 1.线阵相机使用的线扫描传感器通常只有一行感光单元(少数彩色线阵使用三行感光单元的传感器) 2.线阵相机每次只采集一行图像; 3.线阵相机每次只输出一行图像; 4.与传统的面阵相机相比,面阵扫…...

单机开机无感全自动进入B\S架构系统
单机开机无感全自动进入B\S架构系统 标题:单机用jar包启动项目bat(批处理)不弹黑窗口,并设置开机自启,打开浏览器,访问系统。引言:在实际工作中,遇到单机部署的情况,如今…...

大一,如何成为一名fpga工程师?
1、数电(必须掌握的基础),然后进阶学模电(选学), 2、掌握HDL(HDLverilogVHDL)可以选择verilog或者VHDL,建议verilog就行。 3、掌握FPGA设计流程/原理(推…...

MyBatisPlus学习三:Service接口、代码生成器
学习教程 黑马程序员最新MybatisPlus全套视频教程,4小时快速精通mybatis-plus框架 Service接口 简介 在MyBatis-Plus框架中,Service接口的作用是为实体类提供一系列的通用CRUD(增删改查)操作方法。通常情况下,Servi…...

产品经理如何选择城市?
年底,全国性的人口大迁徙即将开始。选择城市,堪称年轻人的“二次投胎”,族望留原籍,家贫走他乡。 古人在选择城市时,主要的考量因素是家族势力,这一点放在当代,大致也成立,如果在老…...

再谈“敏捷”与“瀑布”在产品开发过程中的反思
作为一家专注于软件开发的公司《智创有术》,我们致力于为客户提供创新、高效和可靠的解决方案。通过多年的经验和专业知识,我们已经在行业内建立了良好的声誉,并赢得了客户的信任和支持。 支持各种源码,网站搭建,APP&a…...

设计模式② :交给子类
文章目录 一、前言二、Template Method 模式1. 介绍2. 应用3. 总结 三、Factory Method 模式1. 介绍2. 应用3. 总结 参考内容 一、前言 有时候不想动脑子,就懒得看源码又不像浪费时间所以会看看书,但是又记不住,所以决定开始写"抄书&qu…...
Hive 源码
hive 编译 issue Failed to execute goal com.github.os72:protoc-jar-maven-plugin:3.5.1.1:run (default) on project hive-standalone-metastore: Error resolving artifact: com.google.protobuf:protoc:2.5.0: The following artifacts could not be resolved: com.goog…...

调整几行代码,接口吞吐提升 10 倍,性能调优妙啊!
景 分析过程 总结 背景 公司的一个ToB系统,因为客户使用的也不多,没啥并发要求,就一直没有经过压测。这两天来了一个“大客户”,对并发量提出了要求:核心接口与几个重点使用场景单节点吞吐量要满足最低500/s的要求。 当时一想,500/s吞吐量还不简单。Tomcat按照100个线程…...

MACOS Atrust服务异常
MAC版Atrust服务异常 点击进入办公后出现提示其一: 核心服务未启动,部分功能存在异常,确定重新启动吗? 可能的原因: 1.上次已完全退出客户端 2.核心服务被其他程序优化禁用 点击重新启动后,出现提示&#x…...
LLM大语言模型(四):在ChatGLM3-6B中使用langchain
目录 背景准备工作工具添加LangChain 已实现工具Calculator、Weather Tool配置 自定义工具自定义kuakuawo Agent 多工具使用参考 背景 LangChain是一个用于开发由语言模型驱动的应用程序的框架。它使应用程序能够: 具有上下文意识:将语言模型与上下文源(提示指令&…...

Dubbo入门介绍和实战
1. 引言 Dubbo是一款开源的高性能、轻量级的Java RPC(远程过程调用)框架,旨在解决分布式服务之间的通信问题。本文将介绍Dubbo的基础概念、核心特性以及使用场景,包括实际示例演示。 2. 什么是Dubbo? Dubbo是阿里巴…...

如何实现无人机识别功能
无人机识别算法可以基于不同的传感器和技术,结合多种方法进行实现。以下是一些常见的无人机识别算法和技术: 视觉识别: 图像处理: 使用计算机视觉技术对无人机图像进行处理,包括特征提取、目标检测和跟踪等。深度学习&…...
Python学习笔记(四)流程控制方法
流程控制有三种方法:分支、循环、跳出 流程的控制通过布尔值来实现,分支和循环都需要对一定的条件进行判断,根据判断结果(布尔值)决定下一步要做什么 布尔值通过比较运算符、逻辑运算符来进行判断是True还是False 不…...

【Qt- C++ Qml 交互】
Qt编程指南 VX:hao541022348 ■ 将C对象注册到 QML中,在QML使用C对象■ C对象注册到元对象系统■ Q_INVOKABLE 宏定义是将C 的 函数(方法)声明为元对象系统可调用的函数■ 演示步骤 ■ 将 C类注册到 QML,并在QML声明一…...

ubuntu 20.04 自由切换 python 的版本
问题描述 当前 ubuntu 20.04 默认安装了多个 python 的版本,执行 python 时,默认版本是 Python 2.7.18 zhangszzhangsz:~$ python Python 2.7.18 (default, Jul 1 2022, 12:27:04) [GCC 9.4.0] on linux2 Type "help", "copyright&quo…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...