题意
分别给出\(ml\)和\(md\)对，关于n头奶牛位置的关系，求1号到n号奶牛的最大距离是多少
每一对ml的关系转化成不等式就是： \(A - B \le C\)
相应的，每一对md的关系转化成不等式就是：\(A - B \geq C\) (\(A\)，\(B\)是两头奶牛的位置，\(C\)是他们相差的距离)
思路
看到多元的不等式组，我们就可以考虑使用差分约束来求解此题
ml移项过后成了: \(A \le B + C\)
相当于是：\(B\)向\(A\)做了一条长度为\(C\)的边
md移项过后成了: \(B \le A - C\)
相当于是：\(A\)向\(B\)做了一条长度为\(-C\)的边
做法
因为此题有负边权，所以我们要用spfa来判环
-从一个源点开始求最短路，这条源点连向所有的边，保证图联通。如果有环的话，说明没有合法方案，直接输出\(-1\)
-接下来再从点1(也就是初始点)开始求最短路，如果最终的答案等于初始的极大值，说明他们之间的距离无穷远，直接输出\(-2\)
-最后，如果没有上面的问题，直接输出\(1\) - \(n\)的距离即可
\(Code\)
#include<bits/stdc++.h>
using namespace std;
struct edge{
int u, v, d, nex;
}g[1010100];
//存图
int n, ma, mb, a, b, c, dis[1010100] = {0}, first[1010100] = {0}, cnt = 0, vis[1010100] = {0}, du[1010100] = {0};
void update(int u, int v, int d){
g[++cnt] = (edge){u, v, d, first[u]}, first[u] = cnt;
}
//建图
int spfa(int f){
for(int i = 0; i <= n; i++) du[i] = 0, vis[i] = 0;
memset(dis, 0x3f, sizeof(dis));//初始值赋极大值
queue<int>p;
p.push(f), vis[f] = 1, dis[f] = 0;
while(!p.empty()){
int nex = p.front();
p.pop(), vis[nex] = 0;
for(int i = first[nex]; i; i = g[i].nex){
if(dis[nex] + g[i].d < dis[g[i].v]){
dis[g[i].v] = dis[nex] + g[i].d;
if(!vis[g[i].v]){
vis[g[i].v] = 1, p.push(g[i].v), du[g[i].v]++;
if(du[g[i].v] > n) return -1;//判断是否存在负权环
}
}
}
}
return dis[n] == 0x3f3f3f3f ? -2 : dis[n];//如果没有更新这个点，输出-2
}
int main(){
scanf("%d %d %d", &n, &ma, &mb);
while(ma--){
scanf("%d %d %d", &a, &b, &c);
update(a, b, c);
}
while(mb--){
scanf("%d %d %d", &a, &b, &c);
update(b, a, -c);
}
//根据前面推出来的式子建图
for(int i = 1; i <= n; i++) update(0, i, 0);//源点连接每一个点，防止图不联通
if(spfa(0) == -1) printf("-1");//如果有负权环，输出-1
else printf("%d", spfa(1));
return 0;
}