关键词：
先引用网上的关于差分约束的解释：
一、引例
1、一类不等式组的解
给定n个变量和m个不等式，每个不等式形如 x[i] – x[j] <= a[k] (0 <= i, j < n, 0 <= k < m， a[k]已知)，求 x[n-1] – x[0] 的最大值。例如当n = 4，m = 5，不等式组如图一-1-1所示的情况，求x3 – x0的最大值。
图一-1-1
观察x3 – x0的性质，我们如果可以通过不等式的两两加和得到c个形如 x3 – x0 <= Ti 的不等式，那么 min Ti | 0 <= i < c 就是我们要求的x3 – x0的最大值。于是开始人肉，费尽千辛万苦，终于整理出以下三个不等式：
-
(3) x3 – x0 <= 8
-
(2) + (5) x3 – x0 <= 9
-
(1) + (4) + (5) x3 – x0 <= 7
这里的T等于8， 9， 7，所以min T = 7，答案就是7。的确是7吗？我们再仔细看看，发现的确没有其它情况了。那么问题就是这种方法即使做出来了还是带有问号的，不能确定正确与否，如何系统地解决这类问题呢？
让我们来看另一个问题，这个问题描述相对简单，给定四个小岛以及小岛之间的有向距离，问从第0个岛到第3个岛的最短距离。如图一-1-2所示，箭头指向的线段代表两个小岛之间的有向边，蓝色数字代表距离权值。
图一-1-2
这个问题就是经典的最短路问题。由于这个图比较简单，我们可以枚举所有的路线，发现总共三条路线，如下：
-
0 -> 3 长度为8
-
0 -> 2 -> 3 长度为7+2 = 9
-
0 -> 1 -> 2 -> 3 长度为2 + 3 + 2 = 7
最短路为三条线路中的长度的最小值即7，所以最短路的长度就是7。这和上面的不等式有什么关系呢？还是先来看看最短路求解的原理，看懂原理自然就能想到两者的联系了。
若有负环，则不等式组解不存在：
若存在负环,则已知a+b+c<0。
又已知：
B-A<=c……1
C-B<=a……2
A-C<=b……3
假设存在解A,B,C
2+3得：A-B<=a+b
和1联立得：-c<=A-B<=a+b
又因为：a+b<-c
所以：a+b<a+b，明显不符合，所以解不存在
解的存在性
上文提到最短路的时候，会出现负权圈或者根本就不可达的情况，所以在不等式组转化的图上也有可能出现上述情况，先来看负权圈的情况，如图三-3-1，下图为5个变量5个不等式转化后的图，需要求得是X[t] – X[s]的最大值，可以转化成求s到t的最短路，但是路径中出现负权圈，则表示最短路无限小，即不存在最短路，那么在不等式上的表现即X[t] – X[s] <= T中的T无限小，得出的结论就是 X[t] – X[s]的最大值 不存在。
图三-3-1
再来看另一种情况，即从起点s无法到达t的情况，如图三-3-2，表明X[t]和X[s]之间并没有约束关系，这种情况下X[t] – X[s]的最大值是无限大，这就表明了X[t]和X[s]的取值有无限多种。
图三-3-2
在实际问题中这两种情况会让你给出不同的输出。综上所述，差分约束系统的解有三种情况：1、有解；2、无解；3、无限多解；
差分约束系统(代码片段)
差分约束系统是指由一系列约束条件成的不等式组，形如：即全部是关于两未知数差的不等式一般关于差分约束的题目有两种问法1、是否有解？2、最大解或者最小解解决方法1：设一个超级源点，与每个节点... 查看详情
差分约束刷题记录(代码片段)
把问题转化成一堆不等式，然后用最短路求解POJ3169Layout最后要求1和n之间最大dis是多少 -> 转化为得到一堆 d[n]-d[1]<=xi 然后求xi的最小值对于给出的是d[u]-d[v]>=xi 同乘-1转化为d[v]-d[u]<=-xi即可然后用spfa求1... 查看详情
[luogup1993]小k的农场（差分约束+spfa判断负环）
传送门 差分约束系统。。找负环用spfa就行 ——代码1#include<cstdio>2#include<cstring>3#include<iostream>4#defineN10000156intn,m,cnt;7inthead[N],to[N<<1],val[N<<1],next[N&l 查看详情
poj2983-istheinformationreliable?(差分约束系统)
...存在负环。好久才看明确。对于精确消息。能够得出两个差分公式:dis[v]<=dist[u]-w && dist[u]<=dist[v]+w。对于模糊 查看详情
数字信号处理线性常系数差分方程(根据“线性常系数差分方程“与“边界条件“确定系统是否是“线性时不变系统“案例二|修改边界条件|使用递推方法证明)
文章目录一、根据"线性常系数差分方程"与"边界条件"确定系统是否是"线性时不变系统"案例1、使用递推方法证明2、证明线性3、证明时不变先变换后移位先移位后变换时变系统结论参考【数字信号处理】线性常... 查看详情
g-thematrixproblem(差分约束&判负环优化)(代码片段)
G-THEMATRIXPROBLEM(差分约束&判负环优化)然后转差分约束判负环即可，最好建立一个超级源点，避免图不连通。本题需要判负环的时候优化，即：++in[v]>sqrt(n+m)++in[v]>sqrt(n+m)++in[v]>sqrt(n&... 查看详情
负环与差分约束(代码片段)
...]>dis[x]+v)dis[y]=dis[x]+v;if(!vis[y])q.push(y);vis[y]=true;returnfalse;差分约束差分约束系统即为(n)元一次不等式组，每个约束条件都是由两个变量作差构成的，形如(x_i-x_ileqslantc_k)，目标为求出一组解可以满足所有约束条件(x_i-x_jleqslantc_k)... 查看详情
培训补坑（day5:最小生成树+负环判断+差分约束）
补坑补坑（(╯‵□′)╯︵┻━┻）内容真的多。。。一个一个来吧。首先是最小生成树。先讲一下生成树的定义生成树就是在一张图上选取一些边，使得整个图上所有的点都连通。那么我们要求的最小生成树有两种算法可以求... 查看详情
bzoj1486[hnoi2009]最小圈分数规划+spfa
...负环则调整下界，否则调整上界，直至上下界基本重合。证明：显然 由于有(c+d)/(a+b+k)＞(c+d)/(a+b)≥min(c/a,d/b)，所以两个相交环形成的新环一定不是最优解，即答案一定是简单环。如果存在环使得 查看详情
luogup3275[scoi2011]糖果(代码片段)
思路这个题是近似于差分约束的模板题（稍微难一点点），差分约束我之前好像听yt神仙讲过。不懂差分约束的自行百度。这个题需要注意的就是在建立超级原点的时候要倒叙建边（理论上正倒序都可以，但是这个题正序过不了... 查看详情
poj3159candies（差分约束+spfa+链式前向星）
...数<=C。最后求n比1最多多多少颗糖果。解题思路：经典差分约束的题目，具体证明看这里《数与图的完美结合——浅析差分约束系统》。不妨将糖果数当作距离，把相差的最大糖果数看成 查看详情
didponglie?（差分系统判负环）
DidPongLie?时间限制: 5Sec 内存限制: 128MB提交: 68 解决: 15[提交][状态][讨论版]题目描述DoctorPonghastwoarraysofintegers:a1 ,a2 ,......,aN andb1 ,b2 ,......,b 查看详情
spfa判断负环
...每一个点，然后dfs/bfs更新即可，具体看代码。现在我要证明的是为什么它是正确的。它的基本思想是：如果找到一个点x，能更新自己，那么就存在负环。然而有这样一种情况：由于(dis+v<dis)才能更新的限制，可能点X更新到Y就... 查看详情
差分约束
1.bzoj3436思路:差分约束根据限制条件建图，注意要有一个超级源点向所有点连一条边权为0的边建图看代码。然后spfa判负环，写bfs会超时的......实测n遍。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#defin... 查看详情
差分约束系统
...些完整性,那么我也来一份缺乏完整性(大雾)的总结. 差分约束系统的概念 设$X=left{x_1,x_2,...,x_n ight}$. 满足若干个形如$x_i-x_jgew$的限制条件. 解$X$. 解一个问题有三个大的层次: ①是否存在解?构造任意... 查看详情
机器学习svm中的约束优化问题证明
p1993小k的农场-差分约束(代码片段)
看出不等式之后，通过移项套模型大概不等式模型是这样的：(x_v<=x_u+w_(u,v))(x_v-x_u<=w_(u,v))从减数到被减数连边长得和最短路的三角形不等式似的所以求解也围绕着不等式可以看出(x_v)的最大值就是一条最短路的形式若最短路... 查看详情
怎么搞差分约束？(代码片段)
差分约束是用来解多个不等式中一个什么玩意儿的MAX或MIN或者是这么一大堆式子有没有解v-u>x 巴拉巴拉好多这样的式子看一下最短路是如何运作的 在一张已经维护好的图上有dis[v]<=dis[u]+way[u][v];把上面的式子DuangD... 查看详情