差分约束

图论 / diff-constraints

本地源文件：docs/graph__diff-constraints.md

差分约束

定义

差分约束系统 是一种特殊的 𝑛n 元一次不等式组，它包含 𝑛n 个变量 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn 以及 𝑚m 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 𝑥𝑖 −𝑥𝑗 ≤𝑐𝑘xi−xj≤ck，其中 1 ≤𝑖,𝑗 ≤𝑛,𝑖 ≠𝑗,1 ≤𝑘 ≤𝑚1≤i,j≤n,i≠j,1≤k≤m 并且 𝑐𝑘ck 是常数（可以是非负数，也可以是负数）．我们要解决的问题是：求一组解 𝑥1 =𝑎1,𝑥2 =𝑎2,…,𝑥𝑛 =𝑎𝑛x1=a1,x2=a2,…,xn=an，使得所有的约束条件得到满足，否则判断出无解．

差分约束系统中的每个约束条件 𝑥𝑖 −𝑥𝑗 ≤𝑐𝑘xi−xj≤ck 都可以变形成 𝑥𝑖 ≤𝑥𝑗 +𝑐𝑘xi≤xj+ck，这与单源最短路中的三角形不等式 𝑑𝑖𝑠𝑡[𝑦] ≤𝑑𝑖𝑠𝑡[𝑥] +𝑧dist[y]≤dist[x]+z 非常相似．因此，我们可以把每个变量 𝑥𝑖xi 看做图中的一个结点，对于每个约束条件 𝑥𝑖 −𝑥𝑗 ≤𝑐𝑘xi−xj≤ck，从结点 𝑗j 向结点 𝑖i 连一条长度为 𝑐𝑘ck 的有向边．

注意到，如果 {𝑎1,𝑎2,…,𝑎𝑛}{a1,a2,…,an} 是该差分约束系统的一组解，那么对于任意的常数 𝑑d，{𝑎1 +𝑑,𝑎2 +𝑑,…,𝑎𝑛 +𝑑}{a1+d,a2+d,…,an+d} 显然也是该差分约束系统的一组解，因为这样做差后 𝑑d 刚好被消掉．

过程

设 𝑑𝑖𝑠𝑡[0] =0dist[0]=0 并向每一个点连一条权重为 00 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，𝑥𝑖 =𝑑𝑖𝑠𝑡[𝑖]xi=dist[i] 为该差分约束系统的一组解．

性质

一般使用 Bellman–Ford 或队列优化的 Bellman–Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 𝑂(𝑛𝑚)O(nm)．

常用变形技巧

例题 luogu P1993 小 K 的农场

题目大意：求解差分约束系统，有 𝑚m 条约束条件，每条都为形如 𝑥𝑎 −𝑥𝑏 ≥𝑐𝑘xa−xb≥ck，𝑥𝑎 −𝑥𝑏 ≤𝑐𝑘xa−xb≤ck 或 𝑥𝑎 =𝑥𝑏xa=xb 的形式，判断该差分约束系统有没有解．

题意转化连边
𝑥𝑎 −𝑥𝑏 ≥𝑐xa−xb≥c𝑥𝑏 −𝑥𝑎 ≤ −𝑐xb−xa≤−cadd(a, b, -c);
𝑥𝑎 −𝑥𝑏 ≤𝑐xa−xb≤c𝑥𝑎 −𝑥𝑏 ≤𝑐xa−xb≤cadd(b, a, c);
𝑥𝑎 =𝑥𝑏xa=xb𝑥𝑎 −𝑥𝑏 ≤0, 𝑥𝑏 −𝑥𝑎 ≤0xa−xb≤0, xb−xa≤0add(b, a, 0), add(a, b, 0);

跑判断负环，如果不存在负环，输出 Yes，否则输出 No．

参考代码

---|---

### 例题 [P4926[1007] 倍杀测量者](https://www.luogu.com.cn/problem/P4926)

不考虑二分等其他的东西，这里只论述差分系统 𝑥𝑖𝑥𝑗 ≤𝑐𝑘xixj≤ck![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的求解方法．

对每个 𝑥𝑖,𝑥𝑗xi,xj![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 和 𝑐𝑘ck![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 取一个 loglog![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 就可以把乘法变成加法运算，即 log⁡𝑥𝑖 −log⁡𝑥𝑗 ≤log⁡𝑐𝑘log⁡xi−log⁡xj≤log⁡ck![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，这样就可以用差分约束解决了．

## Bellman–Ford 判负环代码实现

下面是用 Bellman–Ford 算法判断图中是否存在负环的代码实现，请在调用前先保证图是连通的．

实现

C++Python

---|---

---|---

## 习题

[Usaco2006 Dec Wormholes 虫洞](https://loj.ac/problem/10085)

[「SCOI2011」糖果](https://loj.ac/problem/2436)

[POJ 1364 King](http://poj.org/problem?id=1364)

[POJ 2983 Is the Information Reliable?](http://poj.org/problem?id=2983)

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/diff-constraints.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/diff-constraints.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [Anguei](https://github.com/Anguei), [hsfzLZH1](https://github.com/hsfzLZH1), [StudyingFather](https://github.com/StudyingFather), [Enter-tainer](https://github.com/Enter-tainer), [Henry-ZHR](https://github.com/Henry-ZHR), [iamtwz](https://github.com/iamtwz), [Menci](https://github.com/Menci), [Tiphereth-A](https://github.com/Tiphereth-A), [Xeonacid](https://github.com/Xeonacid), [Chrogeek](https://github.com/Chrogeek), [Haohu Shen](mailto:haohu.shen@ucalgary.ca), [ImpleLee](https://github.com/ImpleLee), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [ouuan](https://github.com/ouuan), [shawlleyw](https://github.com/shawlleyw)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用