poj 3169 Layout
题意：
有一排按顺序排列的牛，i在i+1的前面。
牛之间存在2种关系：(i < j)
(i,j,a):i希望离j的距离不超过a；
(i,j,b):i希望离j的距离不小于b；
有可能许多牛是在同一个位置。
给出一些关系，求第一头牛和最后一头牛的距离的最大值。
思路：
通过两个关系可以得出两个不等式
1：d[i] + a >= d[j]
2：d[i] + a <= d[j]
有若干个形如上式的不等式，称为差分约束系统，采用最短路的方式求解。
首先把不等式转化为统一的大于等于的形式（大于等于对应于最短路，小于等于对应于最长路）。
之后，对应于统一的d[i] + a >= d[j]的形式，则添加一条从i到j的权值为a的边；
题中还有隐藏关系d[i] <= d[i+1] + 0，则添加一条从i+1到i的权值为0的边。
因为有负权边，所以用bellman-ford算法。
当第n次还有边更新的时候，说明有负权回路，无解。其他情况有解。
坑：
poj 强行 while (scanf())。。。
版权声明：本文为kickit原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。