給出一組限制條件 a[i] - a[j] ≥ k 或 a[i] - a[j] ≤ k。
要你求出a[t] - a[s]的最小值或最大值。
先舉一個(gè)題目的例子：poj1201.
題目大意是，有一個(gè)集合S。已知其滿足以下一些條件：
對(duì)于給出的n組 a[i] b[i] c[i]，有從a[i]~b[i]這連續(xù)的k個(gè)整數(shù)中，至少有c[i]個(gè)在集合S內(nèi)。求S最少的元素個(gè)數(shù)。
這個(gè)題目轉(zhuǎn)化為我們的差分約束系統(tǒng)如下：
如果i∈S，則t[i]=1，否則t[i]=0。另s[i] = ∑t[j] (j = 0 ~ i)，這樣子，題目的條件就可以用下面的式子表示：
s[b[i]] - s[a[i]-1] ≥ c[i]
s[i] - s[i+1] ≥ -1
s[i+1] - s[i] ≥ 0
注意后面兩個(gè)式子是s先天的性質(zhì)。
我們要求的就是s[n] - s[-1]的最小值（因?yàn)轭}目都是非負(fù)的嘛）。
然后我們介紹解決差分約束問(wèn)題的方法：Bellman-Ford算法，是不是很神奇呢？沒(méi)錯(cuò)，差分約束系統(tǒng)可以通過(guò)轉(zhuǎn)換成圖論最短路問(wèn)題來(lái)解決：
注意到最短路算法的松弛操作：if (d[j] > d[i] + w[i][j]) d[j] = d[i] + w[i][j]。
這其中的三角形不等式：d[j] ≤ d[i] + w[i][j]簡(jiǎn)單變形就成了d[i] - d[j] >=
-w[i][j]。這樣就圖形的最短路就維護(hù)了一個(gè)不等式組。所以，我們可以建立一個(gè)圖：對(duì)于每一個(gè)不等式s[i] - s[j] >=
c，就從j連一條指向i的邊，其中邊的權(quán)值c，這樣求一個(gè)最長(zhǎng)路，就是d[n] - d[-1]就是s[n] -
s[-1]的最小值了，且對(duì)應(yīng)的方案就是s[i] = d[i]。
有的同學(xué)要問(wèn)了：無(wú)解怎么辦啊？很簡(jiǎn)單，你將會(huì)發(fā)現(xiàn)Bellman-Ford算法如果找出了”負(fù)權(quán)回路”，那么該系統(tǒng)無(wú)解。只要系統(tǒng)無(wú)解，就必然存在”負(fù)權(quán)圈”。
那么如果求s[n] - s[-1]的最小值呢？其實(shí)和上面的方法類似了，大家可以自己推導(dǎo)一下。而且有很多問(wèn)題僅僅要你給出是否有解的判斷，那就不要想那么多了。
實(shí)際上是求最長(zhǎng)路，其實(shí)就是把松弛操作的符號(hào)改變即可
其實(shí)此題可以用spfa實(shí)現(xiàn)，效率很高
開(kāi)始做此題時(shí)
連續(xù)超時(shí)很久
此題每次要進(jìn)行三次松弛操作
1 for(int j=Min;j<Max;++j)
2 {
3 if(d[j]!=INT_MIN&&d[j]>d[j+1])
4 {
5 d[j+1]=d[j];
6 update=0;
7 }
8 }
9 for(int j=Max;j>Min;--j)
10 {
11 if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
12 {
13 update=0;
14 d[j-1]=d[j]-1;
15 }
16 }
一開(kāi)始將兩個(gè)松弛操作合并到一起進(jìn)行
超時(shí)
第二次分開(kāi)
仍然超時(shí)
第三次
改變松弛的順序
即第三個(gè)松弛從上到下（之前是從下到上）
這樣做的目的就是避免了重復(fù)的松弛操作！
1 #include <iostream>
2 using namespace std;
3 struct Edge
4 {
5 int x,y,d;
6 }edge[50000+5];
7 int n;
8 int d[50000+5];
9 int main()
10 {
11 while(scanf("%d",&n)!=EOF)
12 {
13 int Min=INT_MAX;
14 int Max=INT_MIN;
15 for(int i=0;i<n;++i)
16 {
17 scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].d);
18 if(--edge[i].x<Min)Min=edge[i].x;
19 if(edge[i].y>Max)Max=edge[i].y;
20 }
21 int tmp=Max-Min+1;
22 for(int i=Min;i<=Max;++i)
23 d[i]=INT_MIN;
24 d[Min]=0;
25 for(int i=0;i<tmp;++i)
26 {
27 bool update=1;
28 for(int j=0;j<n;++j)
29 {
30 if(d[edge[j].x]!=INT_MIN&&d[edge[j].y]<d[edge[j].x]+edge[j].d)
31 {
32 update=0;
33 d[edge[j].y]=d[edge[j].x]+edge[j].d;
34 }
35 }
36 for(int j=Min;j<Max;++j)
37 {
38 if(d[j]!=INT_MIN&&d[j]>d[j+1])
39 {
40 d[j+1]=d[j];
41 update=0;
42 }
43 }
44 for(int j=Max;j>Min;--j)
45 {
46 if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
47 {
48 update=0;
49 d[j-1]=d[j]-1;
50 }
51 }
52 if(update)break;
53 }
54 printf("%d\n",d[Max]-d[Min]);
55 }
56 return 0;
57 }