日記（周六&&差分限制）

    昨天看的部落格其實也是最短路相關的東西，上次沒有看完那些部落格，又看了一下，然後又研究複習，學習了差分限制。我了解的差分限制就是有很多變量x1，x2，x3。。。xn。他們之間有很多限制條件，我們就是根據這些限制條件來建邊，解題。一般有x(n)-x(n-1)<=w。一般不會直接給出這種公式，有些需要自己去推倒。如果是這樣的公式，一般求最大值，可以通過數學知識知道要想算出值，需要找到另一個x(n-1)來抵消-x(n-1)這樣依次遞推下去，這樣感覺就像是再x(n)到x(n-1)之間連了一條邊，從x(n)走到了x(n-1)，那麼要求是最大值，怎麼走才是最大那，當然是取最大值的時候，就是邊權為w的時候。如果要求x(n)到x1的最大值的話，那麼就是求x(n)到x1的連邊，而且x(n)-x(n-1)<=w變為x(n)<=x(n-1)+w，這個和最短路松弛操作類似，如果跑完最短路，d(n)有值的話，那麼，就是有一個最大值，滿足限制條件，完成松弛。如果沒有值，那麼就是這個圖不連通，那麼就需要進行一下操作，建立的圖可能不聯通，我們隻需要加入一個超級源點，比如說求取最長路時圖不聯通的話，我們隻需要加入一個點S，對其他的每個點建立一條權值為0的邊圖就聯通了。既然說到這裡，無論是最短路還是最長路，都會存在環，這樣的話，就不會存在所謂的最大最小值了，那麼就需要判環，用spfa即可，n個點中如果同一個點入隊超過n次，那麼即存在環。

    當x(n)-x(n-1)>=w的話，那麼就是相反的，可以把最短路的松弛操作x(n)<=x(n-1)+w，改一下，就變成(n)>=x(n-1)+w，然後求最長路就行了。

    在差分限制中，有些方程需要轉化。

    1.X[n-1]-X[0]>=T ,可以進行移項轉化為： X[0]-X[n-1]<=-T。

    2.X[n-1]-X[0]<T, 可以轉化為X[n-1]-X[0]<=T-1。

    3.X[n-1]-X[0]=T，可以轉化為X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T，再利用前兩條進行轉化即可。

    有很多類似的不等式，都可以類比的轉化。其他的操作就是最短路了。