题目链接:?id=3169
题意：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啊。
对于差分约束问题我转载了一篇某大牛的文章，说的很详细
用相同的思路求最长路的时候把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当然最好（只要是定值都可以）。
代码实现：
//268K172MS#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define inf 0x7fffffffusing 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<n;i++){for(int j=2;j<=n;j++){if(dis[j]!=inf) dis[j-1]=min(dis[j-1],dis[j]);}for(int j=1;j<=ml+md;j++){if(dis[u[j] ]!=inf) dis[v[j] ]=min(dis[v[j] ],dis[u[j] ]+w[j]);}}}int main(){scanf("%d%d%d",&n,&ml,&md);for(int i=1;i<=ml;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]);for(int i=ml+1;i<=ml+md;i++) {scanf("%d%d%d",&v[i],&u[i],&w[i]);w[i]*=-1;}bellman();for(int i=1;i<=ml+md;i++)if(dis[u[i]]!=inf&&dis[v[i]]>dis[u[i] ]+w[i]) flag=1;if(flag) printf("-1\n");else if(dis[n]==inf) printf("-2\n");else printf("%d\n",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参与其中，既可以判连通也可以判整个分离图的负权环。
的这一半更多地赢取上帝掌握的那一半。
