（例）layout
传送门
题目描述
当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000）你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。
样例
- 输入
4 2 1
1 3 10
2 4 20
2 3 3
- 输出
27
差分约束
借这道题学一下差分约束。
将解几个不等式转化为跑最短/长路。
到底是跑最短路还是最长路看题目是求最大值还是最小值.
- 最短路:求最大值,转化为 \(a-b \le w\) , \(b\) 到 \(a\)建边.
- 最长路:求最小值,转化为 \(a-b \ge w\) , \(b\) 到 \(a\)建边.
以下以最短路为例,最长路大同小异.
解析
\(a-b \le w\)
\(a \le w+b\)
和跑最短路时的状态转移方程类似
可以转化为：从 \(b\) 到 \(a\) 连一条长度为 \(w\) 的边,此时跑最短路求得时满足条件的最大值.
-
为什么求的是最大值呢?
\(a\le w+b\) 下面这个式子中,\(a\) 直接带入的最大值( \(w+b\) ),所以求的是最大值.
-
为什么要跑最短路呢?
因为要满足所有条件,所以要满足所有\(a \le x_i+w_i\) ,因此跑最短路.
if(d[a]>d[b]+w) d[a]=d[b]+w;
本题注意
- \(cow\) 有排列顺序,要从 \(i+1\) 到\(i\) 连一条边.
- 超级原点判环,再跑 \(spfa\) 求值.