差分限制入門+總結

給定一串序列，長度為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到反而是最小值（加負号後）了，不會影響答案，有意思。