当前位置: 首页 > news >正文

差分约束算法

差分约束

差分约束系统包含 m m m个涉及 n n n个变量的差额限制条件,这些差额限制条件每个都是形式为 x i − x j ≤ b ∈ [ 1 , m ] x_i-x_j\leq b_{\in[1,m]} xixjb[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+wdv,即:
d v − d u ≤ w d_v-d_u\leq w dvduw

对比:
x v − x u ≤ b i x_v-x_u\leq b_i xvxubi

因此对于每个限制条件 x v − x u ≤ b i x_v-x_u\leq b_i xvxubi,我们可以在图上给 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+w1x2
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+w2x2+w2x3
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+w3x3+w3x1
x 1 + w 1 + w 2 + w 3 ≥ x 1 x_1+w_1+w_2+w_3 \geq x_1 x1+w1+w2+w3x1
这说明 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]) xixi(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=1nxii=1nxi

证明:

只需证明性质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]xS0
然后我们在跑最短路时强制 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 xujxuj1wj
求和得到:
∑ 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=1kxujxuj1j=1kwj

由于裂项:
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 xukxu0j=1kwj

由于我们指定了 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 xij=1kwj

这给出了此差分约束系统中,满足所有变量都 ≤ 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=1kwj,原因如下,因为刚才经过的边事实上是由 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,ujdisS,uj1=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=1kdisS,ujdisS,uj1=j=1kwj

由于裂项:
d i s S , i = ∑ k j = 1 w j dis_{S,i}=\underset{j=1}{\overset k\sum}w_j disS,i=j=1kwj

因此我们知道 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=1kwj,证明上界可以取到。

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+wdv
d u − d v ≤ − w d_u-d_v\leq -w dudvw
即:
x u − x v ≤ b i x_u-x_v\leq b_i xuxvbi

那么 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]) xixi(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=1nxii=1nxi

证明同理。

其他问题

各类限制转化

通常讨论的差分约束问题往往变量为整数,对于一些其他形式的简单线性不等式可以转化为差分约束问题 x − y ≤ b x-y\leq b xyb
x − y < b ⇒ x − y ≤ b − 1 x-y<b\Rightarrow x-y\leq b-1 xy<bxyb1
x − y ≥ b ⇒ y − x ≤ − b x-y\geq b\Rightarrow y-x\leq -b xybyxb
x − y > b ⇒ y − x < − b x-y>b\Rightarrow y-x<-b xy>byx<b
x − y = b ⇒ x − y ≤ b 且 x − y ≥ b x-y=b\Rightarrow x-y\leq b且x-y\geq b xy=bxybxyb(当然如果全是等式限制直接高斯消元更好)

通常差分约束可能涉及对题意进行差分/前缀和转化。

正解/负解

建最短路得出的解一定是非正解,并且是最大解。
建最长路得出的解一定是非负解,并且是最小解。

同时注意到对一组可行解的每个变量都加 k k k之后,这个解仍然是可行解,因此我们可以获得全正/全负解。

后记

于是皆大欢喜。

相关文章:

差分约束算法

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

彻底解决vue-video-player播放视频有黑边

需求 最近需要接入海康视频摄像头&#xff0c;然后把视频的画面接入到自己的网站系统中。以前对接过rtsp固定IP的显示视频&#xff0c;这次的不一样&#xff0c;没有了固定IP。海康的解决办法是&#xff0c;摄像头通过配置服务器到萤石云平台&#xff0c;然后购买企业版账号和…...

区域负责人常用的ChatGPT通用提示词模板

区域市场分析&#xff1a;如何分析区域市场的特点、竞争态势和客户需求&#xff1f; 区域销售策略制定&#xff1a;如何制定针对区域市场的销售策略&#xff0c;包括产品定位、价格策略、渠道策略等&#xff1f; 区域销售目标设定&#xff1a;如何设定明确的区域销售目标&…...

Java Spring boot 可變參數,以及弊端

function中 不固定的參數 public boolean sendEmail(String manFrom, String manTo,String manCc, String subject, String... msg); 必須是最後一個參數&#xff0c;傳值時可以多個。 sendEmail(“a.gmail”,"b.gmail","c.gmail","subject",…...

机器视觉系统选型-线阵工业相机选型

线阵相机特点&#xff1a; 1.线阵相机使用的线扫描传感器通常只有一行感光单元&#xff08;少数彩色线阵使用三行感光单元的传感器&#xff09; 2.线阵相机每次只采集一行图像&#xff1b; 3.线阵相机每次只输出一行图像&#xff1b; 4.与传统的面阵相机相比&#xff0c;面阵扫…...

单机开机无感全自动进入B\S架构系统

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

大一,如何成为一名fpga工程师?

​ 1、数电&#xff08;必须掌握的基础&#xff09;&#xff0c;然后进阶学模电&#xff08;选学&#xff09;&#xff0c; 2、掌握HDL&#xff08;HDLverilogVHDL&#xff09;可以选择verilog或者VHDL&#xff0c;建议verilog就行。 3、掌握FPGA设计流程/原理&#xff08;推…...

MyBatisPlus学习三:Service接口、代码生成器

学习教程 黑马程序员最新MybatisPlus全套视频教程&#xff0c;4小时快速精通mybatis-plus框架 Service接口 简介 在MyBatis-Plus框架中&#xff0c;Service接口的作用是为实体类提供一系列的通用CRUD&#xff08;增删改查&#xff09;操作方法。通常情况下&#xff0c;Servi…...

产品经理如何选择城市?

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

再谈“敏捷”与“瀑布”在产品开发过程中的反思

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

设计模式② :交给子类

文章目录 一、前言二、Template Method 模式1. 介绍2. 应用3. 总结 三、Factory Method 模式1. 介绍2. 应用3. 总结 参考内容 一、前言 有时候不想动脑子&#xff0c;就懒得看源码又不像浪费时间所以会看看书&#xff0c;但是又记不住&#xff0c;所以决定开始写"抄书&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服务异常 点击进入办公后出现提示其一&#xff1a; 核心服务未启动&#xff0c;部分功能存在异常&#xff0c;确定重新启动吗&#xff1f; 可能的原因&#xff1a; 1.上次已完全退出客户端 2.核心服务被其他程序优化禁用 点击重新启动后&#xff0c;出现提示&#x…...

LLM大语言模型(四):在ChatGLM3-6B中使用langchain

目录 背景准备工作工具添加LangChain 已实现工具Calculator、Weather Tool配置 自定义工具自定义kuakuawo Agent 多工具使用参考 背景 LangChain是一个用于开发由语言模型驱动的应用程序的框架。它使应用程序能够: 具有上下文意识&#xff1a;将语言模型与上下文源(提示指令&…...

Dubbo入门介绍和实战

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

如何实现无人机识别功能

无人机识别算法可以基于不同的传感器和技术&#xff0c;结合多种方法进行实现。以下是一些常见的无人机识别算法和技术&#xff1a; 视觉识别&#xff1a; 图像处理&#xff1a; 使用计算机视觉技术对无人机图像进行处理&#xff0c;包括特征提取、目标检测和跟踪等。深度学习&…...

Python学习笔记(四)流程控制方法

流程控制有三种方法&#xff1a;分支、循环、跳出 流程的控制通过布尔值来实现&#xff0c;分支和循环都需要对一定的条件进行判断&#xff0c;根据判断结果&#xff08;布尔值&#xff09;决定下一步要做什么 布尔值通过比较运算符、逻辑运算符来进行判断是True还是False 不…...

【Qt- C++ Qml 交互】

Qt编程指南 VX&#xff1a;hao541022348 ■ 将C对象注册到 QML中&#xff0c;在QML使用C对象■ C对象注册到元对象系统■ Q_INVOKABLE 宏定义是将C 的 函数&#xff08;方法&#xff09;声明为元对象系统可调用的函数■ 演示步骤 ■ 将 C类注册到 QML&#xff0c;并在QML声明一…...

ubuntu 20.04 自由切换 python 的版本

问题描述 当前 ubuntu 20.04 默认安装了多个 python 的版本&#xff0c;执行 python 时&#xff0c;默认版本是 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年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

优选算法第十二讲:队列 + 宽搜 优先级队列

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

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

动态规划-1035.不相交的线-力扣(LeetCode)

一、题目解析 光看题目要求和例图&#xff0c;感觉这题好麻烦&#xff0c;直线不能相交啊&#xff0c;每个数字只属于一条连线啊等等&#xff0c;但我们结合题目所给的信息和例图的内容&#xff0c;这不就是最长公共子序列吗&#xff1f;&#xff0c;我们把最长公共子序列连线起…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...