差分约束入门+总结

给定一串序列，长度为n。 a 1 , a 2 , a 3 . . . . . . a n a_1,a_2,a_3......a_n a1​,a2​,a3​......an​

并给定m的限制条件，条件的格式为

a i − a j &lt; = c a_i-a_j&lt;=c ai​−aj​<=c

求 a n − a 1 a_n-a_1 an​−a1​的最大值

考虑序列三个数a，b，c

a − b &lt; = v 1 a-b&lt;=v_1 a−b<=v1​

b − c &lt; = v 2 b-c&lt;=v_2 b−c<=v2​

a − c &lt; = v 3 a-c&lt;=v_3 a−c<=v3​

⟹ a − c &lt; = m i n ( v 3 , ( v 1 + v 2 ) ) \Longrightarrow a-c&lt;=min(v_3,(v_1+v_2)) ⟹a−c<=min(v3​,(v1​+v2​))

这个缩小约束条件的过程就是求最短路的过程

所以可以用最短路模型来解决

模型1.给定一串序列 a 1 − a n a_1 - a_n a1​−an​ 并给出若干限制条件 a i − a j &lt; = c a_i - a_j&lt;=c ai​−aj​<=c，要求 a k 1 a_{k1} ak1​ 与 a k 2 a_{k2} ak2​ 的最大可能差值？

方法：对于每个限制条件 a i − a j &lt; = c a_i - a_j&lt;=c ai​−aj​<=c，从点j到点i建立一条边©，求 a k 1 a_{k1} ak1​ 到 a k 2 a_{k2} ak2​ 的最短路即可。

推广 a k 1 a_{k1} ak1​ 与 a k 2 a_{k2} ak2​ 的最小可能差值？

就是反一反

a − b &gt; = v 1 a-b&gt;=v_1 a−b>=v1​

b − c &gt; = v 2 b-c&gt;=v_2 b−c>=v2​

a − c &gt; = v 3 a-c&gt;=v_3 a−c>=v3​

⟹ a − c &gt; = m a x ( v 3 , ( v 1 + v 2 ) ) \Longrightarrow a-c&gt;=max(v_3,(v_1+v_2)) ⟹a−c>=max(v3​,(v1​+v2​))

要满足所有条件，（a-c的）范围扩大，求最长路

模型2.给定一串序列 a 1 − a n a_1 - a_n a1​−an​ 并给出若干限制条件 a i − a j &gt; = c a_i - a_j&gt;=c ai​−aj​>=c，要求 a k 1 a_{k1} ak1​ 与 a k 2 a_{k2} ak2​ 的最小可能差值？

方法：对于每个限制条件 a i − a j &gt; = c a_i - a_j&gt;=c ai​−aj​>=c，从点j到点i建立一条边©，求 a k 2 a_{k2} ak2​ 到 a k 1 a_{k1} ak1​ 的最长路即可。

条件转换：

a − b &lt; = c ⟹ b − a &gt; = c a-b&lt;=c \Longrightarrow b-a&gt;=c a−b<=c⟹b−a>=c

a − b = c ⟹ a − b &lt; = c , b − a &lt; = c a-b=c \Longrightarrow a-b&lt;=c , b-a&lt;=c a−b=c⟹a−b<=c,b−a<=c

…

(简单数学变换)

模型2也可转换为模型1

a − b &gt; = v 1 a-b&gt;=v_1 a−b>=v1​ ``_```` b − a &lt; = − v 1 b-a&lt;=-v_1 b−a<=−v1​

b − c &gt; = v 2 ⟹ b-c&gt;=v_2 \Longrightarrow b−c>=v2​⟹ c − b &lt; = − v 2 c-b&lt;=-v_2 c−b<=−v2​

a − c &gt; = v 3 a-c&gt;=v_3 a−c>=v3​ ``````` c − a &lt; = − v 3 c-a&lt;=-v_3 c−a<=−v3​

求 a k 2 a_{k2} ak2​ 到 a k 1 a_{k1} ak1​ 的最短路

模型2优化.给定一串序列 a 1 − a n a_1 - a_n a1​−an​ 并给出若干限制条件 a i − a j &gt; = c a_i - a_j&gt;=c ai​−aj​>=c，要求 a k 1 a_{k1} ak1​ 与 a k 2 a_{k2} ak2​ 的最小可能差值？

方法：对于每个限制条件 a j − a i &lt; = − c a_j - a_i&lt;=-c aj​−ai​<=−c，从点i到点j建立一条边(-c)，求 a k 1 a_{k1} ak1​ 到 a k 2 a_{k2} ak2​ 的最短路即可。

对于一个求最短路（最长路）约束条件有可能有三种情况：

1.有上界，即有解

2.无解（有负环）

3.任意多的解（约束条件不够强，或者说图不强连通）

有解就是最短路

无解就是有负环，最短路负无穷大

无穷解就是不连通，最短路正无穷大

题目集：

最长路（模板题）

https://blog.csdn.net/wyxxzsy/article/details/82777158

再提一句，超级源点，一开始对于网上加入超级源点，直接计算最短路很不理解，因为加入超级源点之后，源点到每个点的距离至多是0,所以我一度认为，加入超级源点只是为了图的连通性，判断负环而已。

但在最长路模型里不一样，它的权值都是负的，正确的权值是-dis[v],0到反而是最小值（加负号后）了，不会影响答案，有意思。