3 負環及其應用

3.1 判定算法

判斷負環只能用“邊松弛”算法，也就是Bellman-Ford和SPFA算法。這兩個算法都是\(O(NM)\)級別的。因為負環中一定存在一條負邊，使得\(dis_i > dis_j+d(i,j)\)恒成立。因此，在用邊松弛算法時，如果一條邊被松弛超過一定次數，我們就可以判定圖中存在負環。負環則代表環上的邊權和小于0。在負環上走若干圈，則\(dis_i\)可以趨近\(-\infty\)。

Bellman-Ford算法
如果經過\(n\)輪迭代后，仍然有邊可以被更新，則圖中存在負環。
否則，如果在\(n-1\)輪迭代后，如果不能更新任何一條邊，則圖中不存在負環。

SPFA算法
設\(|\Gamma_i|\)表示從源點到\(i\)的最短路包含的邊數。規定\(|\Gamma_S|=0\)。當轉移\(dis_y = dis_x + d(x,y)\)成立時，我們同時令\(|\Gamma_y| = |\Gamma_x| + 1\)。在任意時刻，如果有\(|\Gamma_y| \geq n\)，則圖中有負環。

我們也可以用入隊次數來判斷。如果一個節點被入隊\(n\)次以上，則圖中存在負環。

當然，前面也介紹過一種基于DFS的SPFA判斷負環的方法。這種方法速度較快，但是比較專一。在計算最短路時，效率遠不如基于隊列的SPFA。

3.2 應用

其實比較靈活。只介紹一些比較簡單的應用

圖上二分
極少數題目會出現。由于本人做題不多，這里只能給出一道例題：HNOI2009 最小圈。
由于答案具有單調性——即不存在小于答案的平均值，而一定存在大于等于答案的平均值，我們可以二分求出最小值。設這個平均值為\(\bar{w}\)，那么根據平均值的性質，對于環上的邊\(w_i\)，有\(\sum_{i=1}^{0}(w_i-\bar{w})=0\)。我們二分這個平均值\(\bar{w}\)，然后把每條邊的邊權設置為\(w_i-\bar{w}\)。如果圖中存在一個負環，說明當前平均值合法，可以進一步縮小。時間復雜度可以看作\(\Omega(m\log W)\)。當然，最壞情況還是\(O(nm\log W)\)的。其中\(W\)表示邊權的上下界之差。

差分約束系統
是一種特殊的\(N\)元一次不等式組。其中每一個不等式都形如\(X_i - X_j \leq c_k\)。通過移項，我們可以得到一個不等式：\(X_i \leq X_j + c_k\)。這個不等式酷似我們之前所講到的三角形不等式。我們的目標就是求出一組\(X_i\)使得每一個三角形不等式成立。對于\(X_i - X_j \geq c_k\)的不等式，可以轉換為\(X_j - X_i \leq -c_k\)的形式解決。

注意到如果\(\{X_i\}\)是一組解，那么通過加上一個常數\(c\)，我們可以得到另一組解\(\{X_i+c\}\)。我們不妨假定每一個變量都是負數或0，設\(X_0 = 0\)，令\(X_i \leq 0\)，則\(X_i - X_0 \leq 0\)。我們由\(X_0\)向所有點連一條邊權為0的邊，然后對于所有\(X_i - X_j \leq c_k\)的邊，我們往\(j\)從\(i\)連一條邊。這時，\(X_i\)的實際意義就是從\(0\)點到\(i\)點的最短距離。用最短路算法就可以求出一組負數解。

當構造出來的圖中存在負環，\(X_i\)會被不斷更新：說明\(X_i\)的值始終無法滿足每個不等式。此時這個差分約束系統無解。由于既要求出最短路，又要判斷負環，這里應該使用SPFA。