给出一组限制条件 a[i] - a[j] ≥ k 或 a[i] - a[j] ≤ k。
要你求出a[t] - a[s]的最小值或最大值。
先举一个题目的例子：poj1201.
题目大意是，有一个集合S。已知其满足以下一些条件：
对于给出的n组 a[i] b[i] c[i]，有从a[i]~b[i]这连续的k个整数中，至少有c[i]个在集合S内。求S最少的元素个数。
这个题目转化为我们的差分约束系统如下：
如果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
注意后面两个式子是s先天的性质。
我们要求的就是s[n] - s[-1]的最小值（因为题目都是非负的嘛）。
然后我们介绍解决差分约束问题的方法：Bellman-Ford算法，是不是很神奇呢？没错，差分约束系统可以通过转换成图论最短路问题来解决：
注意到最短路算法的松弛操作：if (d[j] > d[i] + w[i][j]) d[j] = d[i] + w[i][j]。
这其中的三角形不等式：d[j] ≤ d[i] + w[i][j]简单变形就成了d[i] - d[j] >=
-w[i][j]。这样就图形的最短路就维护了一个不等式组。所以，我们可以建立一个图：对于每一个不等式s[i] - s[j] >=
c，就从j连一条指向i的边，其中边的权值c，这样求一个最长路，就是d[n] - d[-1]就是s[n] -
s[-1]的最小值了，且对应的方案就是s[i] = d[i]。
有的同学要问了：无解怎么办啊？很简单，你将会发现Bellman-Ford算法如果找出了”负权回路”，那么该系统无解。只要系统无解，就必然存在”负权圈”。
那么如果求s[n] - s[-1]的最小值呢？其实和上面的方法类似了，大家可以自己推导一下。而且有很多问题仅仅要你给出是否有解的判断，那就不要想那么多了。
实际上是求最长路，其实就是把松弛操作的符号改变即可
其实此题可以用spfa实现，效率很高
开始做此题时
连续超时很久
此题每次要进行三次松弛操作
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 }
一开始将两个松弛操作合并到一起进行
超时
第二次分开
仍然超时
第三次
改变松弛的顺序
即第三个松弛从上到下（之前是从下到上）
这样做的目的就是避免了重复的松弛操作！
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 }