【数学 线性代数】差分约束

前言

C++算法与数据结构
本博文代码打包下载

什么是差分约束

x系列是变量,y系列是常量,差分系统由若干如下不等式组成。
x1-x2 <= y1 x2-x3 <= y2 ⋯ \cdots

可能有负环的最短路

个人习惯:如果存在a指向b的边,则a是b的前置节点,b是a的后续节点。
某差分约束有n个变量(编号从1到n),m个不等式。根据此差分约束建立有向图G。
第一步,n个节点,m条边。每个不等式 x 1 − x 2 < = y 1 都增加边 x 2 → x1 - x2 <=y1都增加边 x2 \rightarrow x1x2<=y1都增加边x2x1,边权位y1。
第二步:增加节点0,0到所有节点都有边,边权为0。
差分系统的变量和0到各节点的最短路一一对应。
性质一:差分约束所有的限制,有向图都有。故:有向图的解一定是差分约束的解。差分约束的解不一定是G的最短路。 ⟺ \iff 差分系统是G的充分不必要条件。
性质二:有向图无解时,差分约束也无解。存在负环时,有向图无解。不失一般性,以3个节点的环为例。有向图有负环时,差分系统有: x1<=x2+y1 x2<=x3+y2 x3 <=x1+y3 x1 <= x1 + y1+y2+y3 即 0 <= y1+y2+y3,和节点1,2,3是负环矛盾。可以用数学归纳法证明。
性质三:令(a1,a2 ⋯ \cdots )是有向图的解,则(a1+d,a2+d ⋯ \cdots )也是差分系统的解。因为:(x1+d)-(x2-d)等于x1-x2。
性质四:在不引入负环的前提下,缩短任意一条边的解仍然是原系统的解。将y1减去正无穷小(此边权变小),构成的新图。如果有解,也是旧系统的解。
推论一:将任何节点i的直接、间接前置节点和i增加一个正数,则新系统的解仍然是老系统的解。如果节点在环上,此环上所有节点都增加。由于环的点都增加了x,故环上的边权不变,故不会引入负环。
性质五:延长任意一条边产生的新解一定不是旧系统的解。产生的新解 x1-x2一定大于y1。
推论二:原始图,如果节点i增加了一个正整数x,则它的直接、间接前置节点都需要增加x或更多。

负环最短路

dis[t][cur]记录最多经过t条边,从0到cur的最短路。
∀ \forall cur ,dis[n][cur] != dis[n-1][cur],说明存在负环。则无解。
第一层循环枚举前置状态,t = 0 to N-1。第二循环枚举各边。
时间复杂度:O(点数边数)

template<class T = int, T iDef = INT_MAX / 2>
class CDisNegativeRing //贝尔曼-福特算法
{
public:bool Dis(int N, vector<tuple<int, int, int>> edgeFromToW, int start) {vector<T> pre(N, iDef);pre[start] = 0;for (int t = 0; t < N; t++) {auto cur = pre;for (const auto& [u, v, w] : edgeFromToW) {cur[v] = min(cur[v], pre[u] + w);}if (t + 1 == N) {for (int i = 0; i < N; i++) {if (pre[i] != cur[i]) { return false; }}}pre.swap(cur);}m_vDis = pre;		return true;}vector<T> m_vDis;
};

最长路

对应的差分系统是:x1-x2 >= y1 x2-x3 >=y2 x3-x1 >=y3
如果存在正环,则无解。
可以延长边,不能缩短边。
节点i和它的直接间接前置节点可以减去一个正数,仍然是解。

样例

【差分约束】P5960 差分约束普及+
【差分约束】P4878 [USACO05DEC] Layout G普及+
如果差分系统无解,本题无解。如果有解,求第N个变量减第一个变量的最大值。如果1不是N的前置节点,则N可无限增大,即无穷大。否则就是最短路相减。
【差分约束】P5590 赛车游戏省选-
本题求边权,任意解,即差分系统的y系列。
【差分约束】 P3275 [SCOI2011] 糖果省选-
本题求最小正整数解,利用拓扑排序和推论一。

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35032.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【linux】虚拟机执行sudo yum isntall perl报错 could not retrieve mirrorlist htt:

项目场景&#xff1a; 提示&#xff1a;虚拟机安装拓展包&#xff0c;sudo yum install perl Virtualbox 在不安装增强功能扩展的情况下, 无法自适应分辨率和共享剪切板等操作 问题描述 原因分析&#xff1a; 提示&#xff1a;这里填写问题的分析&#xff1a; 出现这个错误是因…

网络编程知识预备阶段

1. OSI七层模型 OSI&#xff08;Open System Interconnect&#xff09;七层模型是一种将计算机网络通信协议划分为七个不同层次的标准化框架。每一层都负责不同的功能&#xff0c;从物理连接到应用程序的处理。这种模型有助于不同的系统之间进行通信时&#xff0c;更好地理解和…

我的Gitee

算法与数据结构: 浙海大小趴菜的一些记录 后续也会更新一些项目&#xff0c;小趴菜以后也会变得很厉害

Collection合集(单列集合)

Collection代表单列集合&#xff0c;每个元素&#xff08;数据&#xff09;只包含一个值。Collection实际上是一个泛型接口 Collection集合常用API&#xff1a; 代码实现&#xff1a; Collection集合遍历 遍历方式一&#xff1a;迭代器 迭代器是用来遍历集合的专用方式&#…

旅游类小程序界面设计

产品概述 艾啦游是一款互联网旅游类小程序&#xff0c;致力于国内精品旅游&#xff0c;以及拥有自由行、专属热榜单、出行攻略等诸多功能&#xff0c;汇聚了许多国内的人气景点&#xff0c;与诸多城市的酒店也保持合作&#xff0c;打造一体式旅行服务&#xff0c;更有不断上新…

移动端开发基础与常见布局

一、移动端基础 1.浏览器现状 ⑴.PC端常见浏览器 360浏览器、谷歌浏览器、火狐浏览器、QQ浏览 器、百度浏览器、搜狗浏览器、IE浏览器。 ⑵.移动端常见浏览器 UC浏览器&#xff0c;QQ浏览器&#xff0c;欧朋浏览器&#xff0c; 百度手机浏览器&#xff0c;360安全浏览器&am…

[算法] 贪心--矩阵消除游戏

文章目录 1. 题意2. 思路贪心思路1思路1并不正确思路1为什么是错误的?这道题该如何求解?枚举思路是超时的!枚举 贪心 3. 编码 今天咱们来分享一道基础的贪心题目 -> 矩阵消除游戏 对于贪心算法的题目, 我感觉是对于初学者没必要太注重证明过程, 因为这玩意的变数比较大, …

数学——A. K-divisible Sum + D. Exam in MAC

A. K-divisible Sum 题目&#xff1a; 思路&#xff1a; 以下 “[xxx]” 符号均代表向上取整 我们假设总和是sum&#xff0c;那么就有sum k * cnt 要想最大值最小&#xff0c;肯定是要让sum尽可能小&#xff0c;这样每个元素都能变小 最小情况是 sum 恰好等于 n 时&#…

Docker 》》Docker Compose 》》network 网络 compose

docker 默认的网络 三种模式 # 列出所有当前主机上或Swarm集群上的网络 docker network ls#查看网络详情 docker network inspect network名称# 清除未使用的docker网络 docker network prune -f# 创建网络 ocker network create -d bridge 网络名称 docker network create –s…

RabbitMQ延迟消息

文章目录 延迟消息死信交换机延迟消息延迟消息应用场景 延迟消息 生产者在发送消息的时候指定一个时间&#xff0c;消费者不会立即收到该消息&#xff0c;而是在指定时间之后才收到消息&#xff0c;这就是延迟消息。 比如说这么一个场景&#xff0c;用户下单后将商品库存进行…

phpstudy+phpstorm+xdebug【学习笔记】

配置PHPStudy 配置PHPSTORM phpstorm选择PHP版本 配置DEBUG 设置服务器 编辑配置 学习参考链接&#xff1a;&#xff1a;https://blog.csdn.net/m0_60571842/article/details/133246064

58.Harmonyos NEXT 图片预览组件架构设计与实现原理

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; Harmonyos NEXT 图片预览组件架构设计与实现原理 文章目录 Harmonyos NEXT 图片预览组件架构设计与实现原理效果预览一、组件架构概述1. 核心组件层…

Android 手机启动过程

梳理 为了梳理思路&#xff0c;笔者画了一幅关于 Android 手机启动的过程图片内容纯属个人见解&#xff0c;如有错误&#xff0c;欢迎各位指正

Chat-TTS-UI:文字转语音 - 本地部署方案

Chat-TTS-UI 是一个基于 ChatTTS 模型的本地网页界面,专为满足用户在信息过载时代轻松获取大量文字信息的需求而设计。它支持中英文混合输入、多种音色选择,并提供 API 接口,方便开发者集成到其他应用中。其简洁易用的网页界面、细粒度控制以及 GPU 加速等高级功能,使其广泛…

11. Pandas :操作Excel文件(Excel报表的案例研究)

从一个装有各种 Excel 文件的文件夹开始&#xff0c;这些文件需要被整合到 Excel 报表中。 它们包含了虚构的电信运营商在全美各营业厅的套餐&#xff08;金、银、铜&#xff09;销售情况。每个月有两个文件&#xff0c;子文件夹 new 中的是新用户&#xff0c;子文件夹 existin…

一周学会Flask3 Python Web开发-SQLAlchemy添加数据操作-班级模块

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili SQLAlchemy提供session.add()方法添加model实体数据&#xff0c;以及提供session.commit()提交事务。 首先list.html加一个添…

大型语言模型与强化学习的融合:迈向通用人工智能的新范式——基于基础复现的实验平台构建

1. 引言 大型语言模型&#xff08;LLM&#xff09;在自然语言处理领域的突破&#xff0c;展现了强大的知识存储、推理和生成能力&#xff0c;为人工智能带来了新的可能性。强化学习&#xff08;RL&#xff09;作为一种通过与环境交互学习最优策略的方法&#xff0c;在智能体训…

Axure大屏可视化原型模板及素材:数据可视化的高效解决方案

数据可视化已成为企业决策、运营分析、市场洞察的重要工具。数据可视化大屏&#xff0c;作为数据展示和交互的直观平台&#xff0c;能够实时呈现关键数据&#xff0c;帮助企业快速做出决策。Axure作为原型设计领域的领先工具&#xff0c;以其丰富的组件库、强大的交互设计能力和…

图片填充容器,如何描述

【图片需要完全填充/拉伸以适应容器尺寸&#xff0c;不保持原始比例&#xff0c;使用 object-fit: fill 属性实现】 效果&#xff1a; 代码案例&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8">&l…

缓存和客户端数据存储体系(Ark Data Kit)--- 应用数据持久化(首选项持久化、K-V、关系型数据库)持续更新中...

Core File Kit做怎删改查操作不便&#xff0c;用Ark Data Kit。 功能介绍 ArkData &#xff08;方舟数据管理&#xff09;为开发者提供数据存储、数据管理和数据同步能力&#xff0c;比如联系人应用数据可以保存到数据库中&#xff0c;提供数据库的安全、可靠以及共享访问等管…