差分约束
先言：
我也不知道怎么回事，就打完这四个题，就看完模板之后，就发现，最多也就是一个略微的变形，然后我也很迷瞪，然后就过了。所以这一篇看着玩玩吧，附上几个好博客，要是学习的话，跟随其他这一项，到时候我复习的时候，知道这个。会就好了
算法 ：
差分约束系统是一种特殊的N元一次不等式组，它包含N个变量,以不等式为例，说明。
\[x_1 - x_2 ≤ 10\]\[x_2 - x_5 ≤10\]\[x_3 - x_2 ≤2\]\[x_1 - x_3 ≤ 6\]
然后根据上述的式子，我们寻找\(x_1-x_2\)的最大值是多少，将式子\(3 , 4\)加起来，也就是\(x_1 - x_2≤8\),那么最大值也就是\(8\)，但是第一个式子很显然\(x_1 - x_2≤10\)，10不是更大一些？取10难道不行吗， 那自然是不行的， 就像是你在解决不等式的时候，你用了交集是一样的道理，相对比于10来说，8更精确一些。同样的，也就是8作为合适的最大值，同时，我们发现这一个式子一个三角形不等式。
解的存在性：
1.存在负环，如果路径中出现负环，就表示最短路可以无限小，即不存在最短路
2.方程组转化，如果给定了\(x_1 - x_2 ≥10\) ， 学过算数的人应该知道，都乘以一个\(-1\)就变成上面的那种形式了。
3.终点无法到达， 也就是\(x_n\)不受\(x_1\)的限制，那么也就是说，\(x_n\)和\(x_1\)的关系可以是无穷大，也可以是无穷小，随你的心意了
应用
首先弄清楚谁限制了谁，并且他们的极值是多少，跑最短路还是最长路，个人喜欢建立超级源点。
赞 (0)