Arthur Yoo's Tech Thoughts >> 差分约束系统（POJ 3169 Layout）

有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，可以列出下列差分约束系统的不等式方程组(*)：

1 2 3 4 5 6 7

//查分约束系统_初始形态 d[1] + 10 >= d[3] d[2] + 20 >= d[4] d[2] + 3 <= d[3] d[2] - d[1] >= 0 d[3] - d[2] >= 0 d[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]的最大值。

Read full article from Arthur Yoo's Tech Thoughts » 差分约束系统（POJ 3169 Layout）