【总结】差分约束模型的要点

  只是一些自己想到的东西,记下来以防忘记。

  1. 求解一系列的 f[b] - f[a] <= x 不等式组时,由a向b建权值为x的边,求最短路。有负环时无解,体现为在SPFA中一个点入队超过n次。

  2. 求解一系列的 f[b] - f[a] >= x 不等式组时,由a向b建权值为x的边,求最长路。有正环时无解,体现为在SPFA中一个点入队超过n次。

  3. 当不等式组中有两种不等式时,应转化为一种不等式,再建边、求最短(长)路。f[b] - f[a] == x 可转化为 f[b] - f[a] <= x 与 f[b] - f[a] >= x 的组合。只需判断是否有解时两种建图方式都可以。

  4. 需要判环时若n过大,可以减小入队次数标准以求减小运行时间,例如sqrt(n)次,带来的后果是有可能会出错。(不确定)

  5. 判断不等式组是否有解时,可能没有确定的起点,需要加一个超级源点s,并向所有其它点连一条s到该点权值为0的有向边,再从点s跑SPFA。

  6. 求点s到点t的最短路,即求满足所有不等式的 f[t] - f[s] 的最大值(求最长路时类似)。有些题目中s和t不是确定的,需要自己判断,如果搞反了显然答案是错误的(有向图不同于无向图)。

  7. 注意隐含的不等式,如 sum[i+1] - sum[i] >= 0 等等。

  下面两个博客有非常详细的讲解/习题,很不错:

  http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

  http://blog.csdn.net/consciousman/article/details/53812818

原文地址:https://www.cnblogs.com/doub7e/p/7623060.html