POJ 3169 Layout（差分約束系統）

POJ 3169 Layout（差分約束系統）

題意：n頭牛編號為1到n，按照編號的順序排成一列，每兩頭牛的之間的距離 >= 0。這些牛的距離存在著一些約束關系：1.有ML組（u, v, w）的約束關系，表示牛[u]和牛[v]之間的距離必須 <= w。2.有MD組（u, v, w）的約束關系，表示牛[u]和牛[v]之間的距離必須 >= w。問如果這n頭無法排成隊伍，則輸出-1，如果牛[1]和牛[n]的距離可以無限遠，則輸出-2，否則則輸出牛[1]和牛[n]之間的最大距離。

這是自己第一道差分約束題，居然這種線性規劃還能轉化成圖論最短路模型解決，實在666啊。

對於差分約束問題我轉載了一篇某大牛的文章，說的很詳細www.Bkjia.com

現在來感受一下這種模型轉換的認知，首先單源最短路模型符合差分約束的不等式 d(v) - d(u)<= w(u, v) ,所以找到一組不等式的解就等價於求解dis數組的過程，設定一個源點src後，就把dis[src]=0,用各種最短路算法最終把dis數組從無窮大，松弛到滿足差分約束不等式為止，所以可以得出這個結論： 對於這種有一個未知數定死(dis[src]=0)的差分約束系統，通過最短路徑算法求出來的一組解當中，所有未知數都達到最大值。

用相同的思路求最長路的時候把dis數組初始化成負無窮，那麼設定一個源點（也就是其中一個解是定值0）之後算出來的解有未知數都達到最小值。

所以對於本題來說首先先把差分約束系統找到，試圖用兩個未知數相減的不等式來表示牛之間距離的關系，所以可以把牛的位置用坐標表示，設一個坐標原點,這個原點一定在1號牛的左邊，所以牛的位置間的不等關系為：X(Bl)-X(Al)<=E(A,B)=Dl X(Ad)-X(Bd)<=E(B,A)= -Dd,而且必須把牛按編號順序排成一排所以又有:X(i)-X(i+1)<=E(i+1,i)=0.然後題目讓你求1牛到N牛的最大距離，也就是max(X(N)-X(1))。所以把1號牛的解X(1)定死，通過最短路徑算法求出來的一組解當中，所有未知數都達到最大值，所以此時X(N)-X(1)為最大值，所以可以設1號牛左邊某一固定距離的位置為源點，初始化dis[1]=a，然後最短路算完，得到答案dis[N]-dis[1]，

所以設a的值為0當然最好（只要是定值都可以）。

代碼實現：

//	268K	172MS
#include
#include
#include
#include
#define inf 0x7fffffff
using namespace std;
int n,ml,md,flag;
int u[20100],v[20100],w[20100];
int dis[1100];
void bellman()
{
    fill(dis,dis+n+1,inf);
    dis[1]=0;
    for(int i=1;idis[u[i] ]+w[i]) flag=1;
    if(flag) printf(-1
);
    else if(dis[n]==inf) printf(-2
);
    else printf(%d
,dis[n]);
    return 0;
}

由於這題對多種情況都有可能涉及到：負權環，或者不強連通（dis[n]==inf），或者源點與負全環也不連通（這個時候按題意應該輸出-1而不是-2）

如果考慮到這些可以hack很多一些ac的代碼了（包括我這個），比如源點與負全環不連通，再多一輪循環檢測是否有負全環也無濟於事，因為我用了“dis[u[i]]!=inf”如果是一般的檢測負權環題目可以把inf設小一點，然後把我那個if條件刪掉，照樣可以判斷出負權環，但是這題還要判不連通也就是（dis[n]==inf），所以要保持inf絕對最大值，不能參與松弛過程，所以兩者不能兼得，用bellman只能再用一次bellman單獨判與源點不相連的負權環。這樣就顯得有點笨拙。

當然在正常的SPFA中，也檢測不了與源點不相連的負權環。但是這裡可以有個小技巧，在SPFA使用之前把圖上每個點提前入隊，再執行算法，檢測如果有一個點入隊超過了n次那麼就有負全環，而且這個時候照樣沒把inf參與其中，既可以判連通也可以判整個分離圖的負權環。