?
题意：n头牛编号为1到n，按照编号的顺序排成一列，每两头牛的之间的距离 >= 0。这些牛的距离存在着一些约束关系：1.有ML组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 <= w。2.有MD组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 >= w。问如果这n头无法排成队伍，则输出-1，如果牛[1]和牛[n]的距离可以无限远，则输出-2，否则则输出牛[1]和牛[n]之间的最大距离。
这是自己第一道差分约束题，居然这种线性规划还能转化成图论最短路模型解决，实在666啊。
对于差分约束问题我转载了一篇某大牛的文章，说的很详细www.2cto.com
现在来感受一下这种模型转换的认知，首先单源最短路模型符合差分约束的不等式 d(v) - d(u)<= w(u, v) ,所以找到一组不等式的解就等价于求解dis数组的过程，设定一个源点src后，就把dis[src]=0,用各种最短路算法最终把dis数组从无穷大，松弛到满足差分约束不等式为止，所以可以得出这个结论： 对于这种有一个未知数定死(dis[src]=0)的差分约束系统，通过最短路径算法求出来的一组解当中，所有未知数都达到最大值。
用相同的思路求最长路的时候把dis数组初始化成负无穷，那么设定一个源点（也就是其中一个解是定值0）之后算出来的解有未知数都达到最小值。
所以对于本题来说首先先把差分约束系统找到，试图用两个未知数相减的不等式来表示牛之间距离的关系，所以可以把牛的位置用坐标表示，设一个坐标原点,这个原点一定在1号牛的左边，所以牛的位置间的不等关系为：X(Bl)-X(Al)<=E(A,B)=Dl X(Ad)-X(Bd)<=E(B,A)= -Dd,而且必须把牛按编号顺序排成一排所以又有:X(i)-X(i+1)<=E(i+1,i)=0.然后题目让你求1牛到N牛的最大距离，也就是max(X(N)-X(1))。所以把1号牛的解X(1)定死，通过最短路径算法求出来的一组解当中，所有未知数都达到最大值，所以此时X(N)-X(1)为最大值，所以可以设1号牛左边某一固定距离的位置为源点，初始化dis[1]=a，然后最短路算完，得到答案dis[N]-dis[1]，
所以设a的值为0当然最好（只要是定值都可以）。
代码实现：
?
// 268K 172MS
#include
#include
#include
#include
#define inf 0x7fffffff using namespace std; int n,ml,md,flag; int u[20100],v[20100],w[20100]; int dis[1100]; void bellman() { fill(dis,dis+n+1,inf); dis[1]=0; for(int i=1;i
dis[u[i] ]+w[i]) flag=1; if(flag) printf(-1 ); else if(dis[n]==inf) printf(-2 ); else printf(%d ,dis[n]); return 0; }
此时到这里就把这题解出来了，下面是弱者对于细节的纠结。。。大神就可以忽略啦
?
由于这题对多种情况都有可能涉及到：负权环，或者不强连通（dis[n]==inf），或者源点与负全环也不连通（这个时候按题意应该输出-1而不是-2）
如果考虑到这些可以hack很多一些ac的代码了（包括我这个），比如源点与负全环不连通，再多一轮循环检测是否有负全环也无济于事，因为我用了“dis[u[i]]!=inf”如果是一般的检测负权环题目可以把inf设小一点，然后把我那个if条件删掉，照样可以判断出负权环，但是这题还要判不连通也就是（dis[n]==inf），所以要保持inf绝对最大值，不能参与松弛过程，所以两者不能兼得，用bellman只能再用一次bellman单独判与源点不相连的负权环。这样就显得有点笨拙。
当然在正常的SPFA中，也检测不了与源点不相连的负权环。但是这里可以有个小技巧，在SPFA使用之前把图上每个点提前入队，再执行算法，检测如果有一个点入队超过了n次那么就有负全环，而且这个时候照样没把inf参与其中，既可以判连通也可以判整个分离图的负权环。