关于差分约束的一切

这篇具有很好参考价值的文章主要介绍了关于差分约束的一切。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

观前须知

笔者的博客主页

声明

本文使用 CC BY-NC-SA 4.0 许可

本文为笔者在 OI 学习中的复习向学习笔记。
部分内容会比较简略。
如有好的习题会不断补充。

知识简介

差分约束解决这样一类问题:
给定一个 n 元一次不等式组,让你求出一组解/判定是否有解/算出某个数的最值/算出和的最值……
先从最简单的开始:

P5960 【模板】差分约束

那么怎么做呢?
发现对于形如 \(x_i - x_j \le c\) 的一个不等式可变形为 \(x_i \le x_j + c\)
对于一个这样的不等式组:

\[\begin{cases} x_1 \le x_2 + c_1 \\ x_2 \le x_3 + c_2 \\ x_1 \le x_3 + c_3 \\ \end{cases} \]

可以推出 \(x_1 \le x_3 + \min(c_1 + c_2,c_3)\)
联想一下,这个式子有什么意义呢?

来看这张图:

不难发现,有 \(x_1 \le x_3 + \operatorname{Dis}(x_1,x_3)\)
那么我们可以把三个变量转换为三个点,对于每个约束两个变量关系的不等式,变为图上的一条边!
考虑最短路中的这个式子: \(dis_v \le dis_u + w\)
那么一个形如 \(x_i - x_j \le c\)\(x_i \le x_j + c\) 的式子,
就可以变成图上一条从 \(j\) 指向 \(i\),权值为 \(c\) 的边!
同理,一个形如 \(x_i - x_j \ge c\) 的式子, 可以变为一条从 \(i\) 指向 \(j\),权值为 \(-c\) 的边。
那么图就可以建出来了。
(如果涉及到 \(x_i - x_j < c\) 的式子,可以考虑变为 \(x_i - x_j <= c - 1\) 处理)

值得一提的一个性质
一个这样的不等式组要不然无解,要不然有无数多组解
因为只要有一组解 \(\{ x_1,x_2,x_3,\cdots,x_n\}\)
我们对于每个变量都加上一个相同的值变为 \(\{ x_1+d,x_2+d,x_3+d,\cdots,x_n+d\}\)
不难发现仍然是满足原不等式组的。
那么现在考虑什么情况下无解。

对于这样一个不等式组:

\[\begin{cases} x_1 - x_2 \le 3\\ x_2 - x_3 \le -5\\ x_3 - x_1 \le 1\\ \end{cases} \]

由第一个和第二个不等式相加可以推出 \(x_1 - x_3 \le -2\)
然而再和第三个不等式相加一下会变成 \(0 \le -1\),显然无解。
扩展一下,对于这样一个不等式组:

\[\begin{cases} x_1 - x_2 \le c_1\\ x_2 - x_3 \le c_2\\ \vdots\\ x_{n-1} - x_n \le c_{n-1}\\ x_n - x_1 \le c_n \end{cases} \]

把这 n 个不等式全部相加会变成 \(0 \le \sum c_i\),当且仅当 \(\sum c_i < 0\)时无解。
那么可以发现,这在图上对应了一个负环
所以当且仅当建出来的图上存在负环时无解
判负环用 SPFA,对于不连通的图,添加一个超级源点
从超级源点向所有点连权值为 \(0\) 的边,然后从超级源点跑最短路即可。
若无负环,跑出来的 dis 数组即为一组解。

那么这道板子题,我们就解决了。
代码见:笔者的板子库

但是还不够。
当我们固定源点的值后,我们就可以求出所有点与源点的差的最值
最小值,则跑最长路,求出一个 \(dis_u \ge x\) 的下界。
(这里最长路可以把图的边权全部取相反数,再跑最短路算出)
最大值,则跑最短路,求出一个 \(dis_u \le x\) 的上界。

如果要求所有变量和的最值呢?
例如令所有变量都为非负整数,求最小的变量和(见下面的习题)。
求最小值,我们跑最长路。
一个 \(x_i \ge x_j + c\) 的式子,变为图上一条从 \(j\) 连向 \(i\),权值为 \(c\) 的边(与小于号的形式类似)
建立超级源点,向各点连权值为 \(0\) 的边,并钦定该源点的值为 \(0\) (在代码里体现为dis[0] = 0),相当于让各个点的值都非负。
接下来从超级源点跑最长路,发现 dis 数组正好就是每个点能取的最小值,求和即为答案。

总结一下
由于通常要跑 SPFA,所以差分约束的数据范围一般不会太大。
先确定要跑什么路,再建图。
重点在于建图的时候不要漏掉题目中的隐藏条件

习题

YbtOj 1509 Intervals

对于 \(0\)\(5\times 10^4\) 的每个值建一个变量 \(s_i\) 表示前缀和。
则题目中的条件可变为 \(s_b - s_{a-1} \ge c\)
注意隐藏条件:\(s_i \le s_{i+1}\) 以及 \(s_{i+1} - s_i \le 1\)
建超级源点跑最长路,答案即为 \(s_{5\times 10^4}\)

细节:
由于有 \(s_{-1}\) 存在,对于所有节点编号加一再建图。

Luogu P3275 【SCOI2011】 糖果

求最小变量和,跑最长路。
根据题意建图,对于 \(x_a < x_b\) 的条件变为 \(x_a \le x_b - 1\)
见超级源点跑最长路,答案为 \(\sum dis_i\)

这道题数据范围较大,差分约束会被 Hack 掉
然而笔者特判自环 + SPFA SLF-swap优化冲过去了

USACO 05DEC Layout G

\(d_i\) 表示前缀距离。
按照题意建图,隐藏条件 \(d_i - d_{i+1} \le 0\)
建超级源点跑最短路,有负环则无解。
对于 1 号节点跑最短路,若与 n 号节点联通则 \(dis_n\) 即为答案,否则两点间距离可以任意大。文章来源地址https://www.toymoban.com/news/detail-845416.html

到了这里,关于关于差分约束的一切的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 关于堆的一切

    首先给出堆的定义: 堆是一颗树,满足堆的性质,即: 对于一个节点,它的权值大于(或小于)它的各个儿子的权值 有这个性质,显然 堆的根节点权值是整个堆中最大或最小的 由此可分为 小根堆 和 大根堆 最常见的堆就是二叉堆 二叉堆是一颗满足 堆的性质 的 完全二叉树

    2024年03月13日
    浏览(35)
  • 关于基环树的一切

    本文使用 CC BY-NC-SA 4.0 许可 。 本文为笔者在 OI 学习中的复习向学习笔记。 部分内容会比较简略。 如有好的习题会不断补充。 基环树 是一个有 (n) 个点 (n) 条边的连通图。 因为 树 有 (n) 个点 (n-1) 条边。 所以基环树可以看作是加了一条边的树。 那么也就是 加了个环的

    2024年04月08日
    浏览(34)
  • 关于树的直径的一切

    本文使用 CC BY-NC-SA 4.0 许可 。 本文为笔者在 OI 学习中的复习向学习笔记。 部分内容会比较简略。 如有好的习题会不断补充。 以下部分详细证明可见 OI Wiki 。 树的直径 指树上任意两点间距离的最大值。 先以任意点为根找到最远点 (v) 。 再以 (v) 为根找到最远点 (u) 。

    2024年04月08日
    浏览(46)
  • 【算法】关于排序你应该知道的一切(下)

    和光同尘_我的个人主页 单程孤舟,出云入霞,如歌如吟。 --门孔 啊还是国庆快乐!上节介绍了较为简单的插入排序、选择排序,今天我们上强度,学习交换排序、归并排序还有计数排序,开冲😎 2.1.1. 基本思想 关于冒泡排序我们在C语言的学习中就有涉及 依次比较序列中相

    2024年02月07日
    浏览(44)
  • 关于web3营销的一切知识

    Web3 时而神秘代表未来、有时又充满黑暗与欺骗。因为 Web3 与科技和金融紧密相关,而这两者又代表着当今世界的方向与人性。有很多人在说,Web3 就是数据的归属权转移,而我认为除此之外,Web3 更是社会里众多组织架构、利益关系、资源配置等等的重构。在目前常见的 cr

    2024年02月08日
    浏览(44)
  • 【算法】关于排序你应该知道的一切(上)

    和光同尘_我的个人主页 单程孤舟,出云入霞,如歌如吟。 --门孔 国庆快乐!!本来想把排序都做到一起的,才写了一半就八千多字了,那就分开发吧,一如既往的详细哦⌨️ 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来

    2024年02月06日
    浏览(35)
  • 【数据结构】关于排序你应该知道的一切(下)

    和光同尘_我的个人主页 单程孤舟,出云入霞,如歌如吟。 --门孔 啊还是国庆快乐!上节介绍了较为简单的插入排序、选择排序,今天我们上强度,学习交换排序、归并排序还有计数排序,开冲😎 2.1.1. 基本思想 关于冒泡排序我们在C语言的学习中就有涉及 依次比较序列中相

    2024年02月05日
    浏览(37)
  • 我们所知道的关于 OpenAI 的 ChatGPT 的一切

    如果您还没有听说过ChatGPT,这是来自人工智能实验室 OpenAI 的不可思议的新聊天机器人,这里是您需要了解的有关这个有争议的新程序的所有信息的快速入门。 ChatGPT 是一种人工智能工具,允许用户生成原始文本。你可以问它问题,给它创造性的提示,并用它来生成一大堆不

    2023年04月13日
    浏览(42)
  • MacOS Sonoma 指南:关于 macOS 14 你需要知道的一切

    macOS Sonoma(以前称为 macOS 10.12 Sierra)是苹果公司开发的操作系统。它是 macOS 的第十三个主要版本。此 macOS 版本引入了许多新功能,包括 Siri 集成、通用剪贴板、iCloud 驱动器同步、画中画视频播放、选项卡式应用程序、Apple Pay 与 Safari 的集成、Apple Music 和地图更新等。macOS

    2024年02月07日
    浏览(51)
  • python安装三方库教程:关于pip命令的一切,到底怎么用?

      看这篇文章的目录,大家会发现写的很详细,适合收藏哦。如果你是刚学python的小白也没关系!看完这篇文章,关于pip的一切你就懂了。   关于pip的命令需要使用命令行,那么打开命令行界面: win+s/win+r快捷键都行,然后输入cmd后回车就能调出命令行界面了   python以

    2023年04月27日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包