http://poj.org/problem?id=3169
对所有的d[i]进行初始化：d[1]=0; d[i] = +INF（i=2,...N）。最后用最短路径的算法（Bellman-Ford或SPFA）来求解，得到的d[N]就是”牛1与牛N之间的最大距离“，即d[N] = 27（N=4）。
对所有的d[i]进行初始化：d[1]=0; d[i] = -INF（i=2,...N）。最后用最短路径的算法来求解，得到的d[N]就是”牛1与牛N之间的最小距离"，此时d[N] = 3（N=4）。
Description
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Input
Line 1: Three space-separated integers: N, ML, and MD.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.
Sample Input
4 2 1 1 3 10 2 4 20 2 3 3
Sample Output
27
http://tech.artyoo.me/?p=163
有N头牛，依次编号为1…N，并且按照编号大小的先后顺序排成一列。有些牛之间比较亲密，它们之间的距离不能大于某个值；有些牛之间相互厌恶，它们之间的距离必须大于某个值。求出满足上述条件中，第1头牛和第N头之间的最大距离；若无法实现，输出-1；若第1头牛和第N头之间可以相隔任意远的距离，则输出-2。首先，设d[i]为第i头牛距离座标起点的距离。根据题意，那些亲密的牛之间的距离必须小于某些值w，则对应不等式方程d[i] + w >= d[j]；相互厌恶的牛之间的距离必须大于某些值w，对应的不等式方程d[i] + w <= d[j]。另外，题目中还有提到“ The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate). ”也就是说，编号大的牛的位置一定要大于等于编号小的牛，但允许编号相邻的牛“挤”在一个点上。所以，据此可以对从前往后的所有牛列出不等式方程d[i+1] – d[i] >= 0（1<= i<N）。到这里，根据POJ 3169的Sample Input，可以列出下列差分约束系统的不等式方程组(*)：
//查分约束系统_初始形态d[1] + 10 >= d[3]d[2] + 20 >= d[4]d[2] + 3 <= d[3]d[2] - d[1] >= 0d[3] - d[2] >= 0d[4] - d[3] >= 0像上面的这样一组一次不等式方程组，每一个不等式方程斗都含有两个正负号相反的变量（d[i]和d[j]），以及一个常数，这样的一次不等式方程组就叫做查分约束系统。假如上面的不等式组进行适当的变换，就能够将所有的变量移动到不等式符号的右侧，而且所有的不等式号也能统一成一种（大于等于号或小于等于号）。用更为简洁的表述来描述上述的查分约束系统就是形如Ax=B，如：题目最后要求的是满足差分约束系统的所有d[i]（1<=i<=N）中，d[N]-d[1]的最大值。由于没有初始条件，如果得到了满足查分约束系统的某一组可行解(d[1], d[2], ..., d[N])的话，那么(d[1]+x, d[2]+x, ..., d[N]+x)也是一组可行解（x是任意实数）。也就是说，在各组可行解中，解向量中的某两个元素之间的差值是定值，即(d[i]+x) - (d[j]+x) 恒等于 d[i] - d[j]。因此，无论得到的可行解的具体数值是多少，题目要求的d[N]-d[1]的最大值肯定的确定的。因此，不妨将d[1]假设为0，那么求d[N]-d[1]的最大值就等价于求d[N]的最大值。
求解查分约束系统中的最大值/最小值问题，一种巧妙的方法是转化成图论的最短路径模型来求解。比如，有一条从u指向v的有向边，其权值为w。求解最短路径的松弛操作为：
if(d[v] >= d[u] + w)d[v] = d[u] + w;也就是说，经过松弛操作之后，最后保证了d[v] <= d[u] + w，再变形一下，即为d[v] - d[u] <= w。同样地，求解最长路径的松弛操作为:
if(d[v] <= d[u] + w)d[v] = d[u] + w;在这里，经过松弛操作之后，最后保证了d[v] >= d[u] + w，再变形一下，即为d[v] - d[u] >= w。
以上的d[i]的含义是“点i到点1的最短/最长路径”。也就是说，在最短路径中，最后求解出来的(d[1], d[2], ..., d[N])必定满足：对于某条j指向i的有向边，都满足d[j] - d[i] <= w（i, j都是图中的顶点， w是从i指向j的有向边的权值；1为起点，即d[1]等于0）。相对应地，最长路径最后求得的解向量的含义也一样，即最后求解出来的(d[1], d[2], ..., d[N])必定满足：对于某条j指向i的有向边，都满足d[j] - d[i] >= w。
所以，最短路径最后所有保证的不等式（d[v] - d[u] <= w）和最长路径最后保证的所有不等式（d[v] - d[u] >= w）完全符合查分约束系统中的不等式方程组的形式。因此，本文上面列出的原始的差分约束系统中不等式方程组(*)有两种变形方向：（1）将所有不等式全部转化成d[v] - d[u] <= w的形式（即将差分约束系统转化为最短路径问题）；（2）将所有不等式全部转化成d[v] - d[u] >= w的形式（即将差分约束系统转化为最长路径问题）。我们再可以假定d[0]=0，即根据最短/最长路径的一般原则来为差分约束系统定一个初始化值（因为我们最后求的是差分约束系统中d[N]-d[1]的最大值，与d[i]的具体值无关）。这样，求解d[N]-d[1]的最大值就转化为了求解d[N]的最大值。在最短路径和最长路径中，d[N]的含义分别是这样的：在最短路径中，d[N]代表“从起点1到点N的最短路径的长度”；在最长路径中，d[N]代表“从起点1到点N的最长路径的长度”。上面是从图论的最短/最长路径的角度来解释d[N]的含义。那么，假如看问题的角度回到差分约束系统，那么d[N]的最大值究竟就是对应最短路径中的d[N]还是最长路径中的d[N]呢？一般来说（我也没有严格地理论化证明过），最短路径中的d[N]对应差分约束系统中d[N]的最大值；最长路径中的d[N]对应差分约束系统中d[N]的最小值（这和人的直觉正好相反）。具体的一个简单的证明在下面会给出。也就是说，本题POJ 3169是要求符合题目所有给出的条件的情况下，第N头牛和第1头牛之间的最大距离（即d[N]的最大值），则应该将差分约束系统转化为最短路径来求解；而假如题目是要求符合题目所有给出的条件的情况下，第N头牛和第1头牛的最短距离（即d[N]的最小值），则应该将差分约束系统转化为最长路径来求解。
为了便于比较和加深理解，我觉得有必要对求解”1牛与N牛之间的最大距离“和”1牛和N牛之间的最短距离“的转化分别都进行描述。
为了求解“1牛与N牛之间的最大距离”，先应该将上文给出的差分约束系统中不等式方程组(*)转化为最短路径最后保证的不等式的形式，即d[v] - d[u] <= w。因此，原来的差分约束系统中不等式方程组(*)变形为：
1
2
3
4
5
6
7
| //原始的差分约束系统中不等式方程组(*)变形为最短路径松弛操作后的形式d[3] - d[1] <= 10d[4] - d[2] <= 20d[2] - d[3] <= -3d[1] - d[2] <= 0d[2] - d[3] <= 0d[3] - d[4] <= 0 |
上面每个不等式的形式为d[v] - d[u] <= w，即d[终点] - d[起点] <= 该有向边的权值。因此，我们可以根据这些不等式构建出转化为最短路径后相应的带权有向图：
对所有的d[i]进行初始化：d[1]=0; d[i] = +INF（i=2,...N）。最后用最短路径的算法（Bellman-Ford或SPFA）来求解，得到的d[N]就是”牛1与牛N之间的最大距离“，即d[N] = 27（N=4）。
相对应的，假如求解”1牛与N牛之间的最小距离“，先应该将上文给出的差分约束系统中不等式方程组(*)转化为最长路径最后保证的不等式的形式，即d[v] - d[u] >= w。因此，原来的差分约束系统中不等式方程组(*)变形为：
1
2
3
4
5
6
7
| //原始的差分约束系统中不等式方程组（*）变形为最短路径松弛操作后的形式d[1] - d[3] >= -10d[2] - d[4] >= -20d[3] - d[2] >= 3d[2] - d[1] >= 0d[3] - d[2] >= 0d[4] - d[3] >= 0 |
上面每个不等式的形式为d[v] - d[u] >= w，即d[终点] - d[起点] >= 该有向边的权值。因此，我们可以根据这些不等式构建出转化为最长路径后相应的带权有向图：
对所有的d[i]进行初始化：d[1]=0; d[i] = -INF（i=2,...N）。最后用最短路径的算法来求解，得到的d[N]就是”牛1与牛N之间的最小距离"，此时d[N] = 3（N=4）。
在这里，可以清楚地看到，将原始的差分约束系统中不等式方程组(*)，分别根据转化成最短路径和最长路径最后所保证的两种形式之后，得到相应变形后的不等式组，然后再依据这两种不同形式的不等式组（本质上三种形式的不等式组都等价）构建出来的带权有向图是不一样的。
之前提到过，通过最短路径算法求出的d[N]对应了差分约束系统中d[N]的最大值；通过最长路径算法求出的d[N]对应了差分约束系统中d[N]的最小值。现在给出一个非正式的证明[1]：
“ 对于这种有一个未知数定死（Arthur：即设d[1]等于0）的差分约束系统，还有一个有趣的性质，那就是通过最短路径算法求出来的一组解当中，所有未知数都达到最大值。下面我来粗略地证明一下，这个证明过程要结合Bellman-Ford算法的过程来说明。
假设X0是定死的；X1到Xn在满足所有约束的情况下可以取到的最大值分别为M1、M2、……、Mn（当然我们不知道它们的值是多少）；解出的源点到每个点的最短路径长度为D1、D2、……、Dn。
基本的Bellman-Ford算法是一开始初始化D1到Dn都是无穷大。然后检查所有的边对应的三角形不等式，一但发现有不满足三角形不等式的情况，则更新对应的D值。最后求出来的D1到Dn就是源点到每个点的最短路径长度。
如果我们一开始初始化D1、D2、……、Dn的值分别为M1、M2、……、Mn，则由于它们全都满足三角形不等式（我们刚才已经假设M1到Mn是一组合法的解），则Bellman-Ford算法不会再更新任合D值，则最后得出的解就是M1、M2、……、Mn。
好了，现在知道了，初始值无穷大时，算出来的是D1、D2、……、Dn；初始值比较小的时候算出来的则是M1、M2、……、Mn。大家用的是同样的算法，同样的计算过程，总不可能初始值大的算出来的结果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。
那么如果在一个未知数定死的情况下，要求其它所有未知数的最小值怎么办？只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反：
d(v) >= d(u) + w(u, v)
也就是 d(v) - d(u) >= w(u, v)”
假设X0是定死的；X1到Xn在满足所有约束的情况下可以取到的最大值分别为M1、M2、……、Mn（当然我们不知道它们的值是多少）；解出的源点到每个点的最短路径长度为D1、D2、……、Dn。
基本的Bellman-Ford算法是一开始初始化D1到Dn都是无穷大。然后检查所有的边对应的三角形不等式，一但发现有不满足三角形不等式的情况，则更新对应的D值。最后求出来的D1到Dn就是源点到每个点的最短路径长度。
如果我们一开始初始化D1、D2、……、Dn的值分别为M1、M2、……、Mn，则由于它们全都满足三角形不等式（我们刚才已经假设M1到Mn是一组合法的解），则Bellman-Ford算法不会再更新任合D值，则最后得出的解就是M1、M2、……、Mn。
好了，现在知道了，初始值无穷大时，算出来的是D1、D2、……、Dn；初始值比较小的时候算出来的则是M1、M2、……、Mn。大家用的是同样的算法，同样的计算过程，总不可能初始值大的算出来的结果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。
那么如果在一个未知数定死的情况下，要求其它所有未知数的最小值怎么办？只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反：
d(v) >= d(u) + w(u, v)
也就是 d(v) - d(u) >= w(u, v)”
因此，有了以上的理论分析后，对于POJ 3169最后要求的是”牛1与牛N之间的最大距离“，即对应上面第一种，我就可以转化为最短路径的模型来求解问题。
代码基本上就是一个很裸的SPFA算法。主要就是最后对于输出情况的判断。本题中的图肯定是联通的，假如SPFA发现图中有负环存在，则肯定有d[i]可以无限地松弛下去，所以，"如果出现负环，说明各种约束不能同时成立"[2]，即无法找到一组满足差分约束系统的解，此时输出-1；假如最后得到d[N]等于正无穷大，则表明牛N和牛1之间的距离可以达到正无穷大，因此输出-2。
因此，对于差分约束系统的题目，我总结下来的基本做法是，首先理解题意，根据题意挖掘出所有差分不等式；然后根据情况判断是求最小值还是最大值，相应地就可以转换为求最长路径还是最短路径的模型来解题了。
int N, ML, MD;int first[MAXN], next[MAXM];int u[MAXM], v[MAXM], w[MAXM];int e;int vis[MAXN], d[MAXN], cnt[MAXN];queue<int> q;int Min(int a,int b){return a<b?a:b;}int Max(int a,int b){return a>b?a:b;}bool spfa() { memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); for(int i = 2; i <= N; i++) d[i] = INF; d[1] = 0; q.push(1); cnt[1]++; while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; for(int ee = first[x]; ee != -1; ee = next[ee]) { if(d[v[ee]] > d[u[ee]] + w[ee]) { d[v[ee]] = d[u[ee]] + w[ee]; if(!vis[v[ee]]) { if(cnt[ee] >= N) { printf("-1\n"); while(!q.empty()) q.pop(); return false; } vis[v[ee]] = 1; q.push(v[ee]); cnt[v[ee]]++; } } } } return true;}int main() { read; write; scanf("%d %d %d\n", &N, &ML, &MD); memset(first, -1, sizeof(first)); e = 0; int a, b, c; for(int i = 1; i <= ML; i++) { e++; scanf("%d %d %d\n", &a, &b, &c); u[e] = a; v[e] = b; w[e] = c; next[e] = first[u[e]]; first[u[e]] = e; } for(int i = 1; i <= MD; i++) { e++; scanf("%d %d %d\n", &a, &b, &c); u[e] = b; v[e] = a; w[e] = -c; next[e] = first[u[e]]; first[u[e]] = e; } for(int i = 1; i < N; i++) { e++; u[e] = i+1; v[e] = i; w[e] = 0; next[e] = first[u[e]]; first[u[e]] = e; } if(spfa()) { if(d[N] >= INF) puts("-2"); else printf("%d\n", d[N]); } return 0;}