算法

设 \(dis_i\) 表示第 \(i\) 头奶牛的坐标
题目转化为

对于 \(M_L\) 对数对 \((A_i, B_i) , A_i < B_i\) , 使得 \(dis_{B_i} - dis_{A_i} \leq D_i\)
对于 \(M_D\) 对数对 \((A_i, B_i) , A_i < B_i\) , 使得 \(dis_{B_i} - dis_{A_i} \geq D_i\)
对于 \((i, i + 1)\) , 有 \(dis_{i + 1} \geq dis_i, dis_i \leq dis_{i + 1}\)

两组约束不好处理, 考虑转化成一组约束

对于 \(M_L\) 对数对 \((A_i, B_i) , A_i < B_i\) , 使得 \(dis_{B_i} - dis_{A_i} \leq D_i\)
对于 \(M_D\) 对数对 \((A_i, B_i) , A_i < B_i\) , 使得 \(dis_{A_i} - dis_{B_i} \leq -D_i\)
对于 \((i, i + 1)\) , 有 \(dis_{i} \leq dis_{i + 1}\)

建立超级源点 \(0\) , 避免图不连通

考虑问题中三个结果

有解

先从 \(0\) 开始, 没有负环
再从 \(1\) 开始跑最短路

• 存在最大值
  即为满足约束的最大距离
• 不存在最大值
  分析满足这种情况的图长什么样
  若 \(1\) 和 \(N\) 不连通, 则此时没有直接约束, 输出 \(-2\)

无解

先从 \(0\) 开始, 有负环则无解

代码

后补

总结

对于这样的一类题:

1. 转化为单组约束
2. 判断是否有解(先要有解才能继续讨论), 使用超级源点解决连通性问题
3. 判断是否有约束(这个不是所有题都要用)