差分约束

Aoki_灏 · 2018-08-18 17:57:36 · 个人记录

这其实是个挺常规的算法，今日模拟赛考到了就来写篇博客复习一下

参考原博

差分约束

定义

    如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),
    则称其为差分约束系统。

实例

    给定n个变量和m个不等式，每个不等式的形式为 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m， a[k]已知)，求 x[i] - x[j] 的最大值。
    例如当n = 4，m = 5，给出如下图所示的不等式组，求x3 - x0的最大值。

    一般思路：我们可以尝试把几个不等式组合得到最后我们要求的式子，于是这些式子里最小的那个就是答案。
   比如，在这个例子中：
     （3） ==》  x3 - x0<=4；
     （1）、（4）、（5） ==》 x3 - x0<=5；
     （2）、（5） ==》 x3 - x0<=3;
      所以最后结果就是3.

差分约束与最短路模型

    其实解多个不等式的问题就是一个spfa找最短路或最长路的过程
    x1-x0<=1===> x1>=x0+1;
    这就可以看成最短路的松弛操作
    对于多个<= 就用最短路跑
    多个>= 就用最长路

问题解的存在性

存在负环

    如果路径中出现负环，就表示最短路可以无限小，即不存在最短路，
    那么在不等式上的表现即X[n-1] - X[0] <= T中的T无限小，
    得出的结论就是 X[n-1] - X[0]的最大值不存在。
    在SPFA实现过程中体现为某一点的入队次数大于节点数。（貌似可以用sqrt(num_node)来代替减少运行时间）

终点不可达

     这种情况表明X[n-1]和X[0]之间没有约束关系，
     X[n-1] - X[0]的最大值无限大，即X[n-1]和X[0]的取值有无限多种。
     在代码实现过程中体现为dis[n-1]=INF。

不等式组的转化

     方程给出：X[n-1]-X[0]>=T ,可以进行移项转化为： X[0]-X[n-1]<=-T。
     方程给出：X[n-1]-X[0]<T, 可以转化为X[n-1]-X[0]<=T-1。
     方程给出：X[n-1]-X[0]=T，可以转化为X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T，再利用（1）进行转化即可

相关题

P1993 小k的农场

P2294 HNOI2005狡猾的商人

P3275 SCOI2011糖果

这都是比较基础的题