什么是差分約束系統(tǒng)？
差分約束系統(tǒng)是一種特殊的N元一次不等式組，它包含N個變量以及M個約束條件，每個約束條件都是由兩個變量作差得到的，形如
，其中
是常數(shù)。
我們根據(jù)題目要求，并用這M個約束條件求出某個不等式的最值，例如
的最大值。
怎么解？
轉(zhuǎn)化：
把上面
不等式稍微變形一下可以得到
，令
，
，
，得到
，是不是聯(lián)想到了最短路算法？
因此我們可以把這M個不等式轉(zhuǎn)化到圖中，例如對于
，則在圖中連一條從 j 到 i 的有向邊，邊權(quán)為
。
這時候假如題目需要我們求
的最大值，我們便從圖中求出1到N的最短路即可。
為什么是最短路？由于有約束條件，圖中可能有更長的路的存在，但是如果選了更長的路，那么就不滿足最短路那一條路的約束條件了，即最短路是所有滿足條件的路中最長的一條。
解的存在性：
我們知道不等式的解有三種情況：有解、無解、無限個解。
這三種情況對應(yīng)圖中的情況分別是什么樣的呢？
有解：在圖中可以找到最短路。
無解：圖中存在負環(huán)，沒有最短路。
無限個解：圖中我們要求的兩點間無法到達，即不連通。
最小值：
如果題目給出的條件形如
，最后要我們求出
的最小值，顯然求出1到N的最長路即可。
不等式標準化：
如果題目給出的約束條件既有"≥"也有"≤"該怎么辦？
根據(jù)題目要求，如果需要求最大值，那么把不等式都轉(zhuǎn)化為"≤"，否則轉(zhuǎn)化為"≥"的形式。
但是要是題目給出了等式該怎么辦？
例如
，那么我們可將其轉(zhuǎn)化成兩個不等式：
和
。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習題和答疑，點擊了解：
一點編程也不會寫的：零基礎(chǔ)C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程