主题

主题

 
   

差分约束系统

  • 处理问题

大概是多个形如x-y<=C的模式。

在给出多个式子之后,可以解决x-y的最大值。

(以下大部分源自http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html


  • 处理方法

观察 x[i] - x[j] <= a[k], 将这个不等式稍稍变形,将x[j]移到不等式右边,则有x[i] <= x[j] + a[k],然后我们令a[k] = w(j, i),再将不等式中的i和j变量替换掉,i = v, j = u,将x数组的名字改成d(以上都是等价变换,不会改变原有不等式的性质),则原先的不等式变成了以下形式:d[u] + w(u, v) >= d[v]。

这时候联想到SPFA中的一个松弛操作:

if(d[u] + w(u, v) < d[v]) {d[v] = d[u] + w(u, v);}

对比上面的不等式,两个不等式的不等号正好相反,但是再仔细一想,其实它们的逻辑是一致的,因为SPFA的松弛操作是在满足小于的情况下进行松弛,力求达到d[u] + w(u, v) >= d[v],而我们之前令a[k] = w(j, i),所以我们可以将每个不等式转化成图上的有向边:

对于每个不等式 x[i] - x[j] <= a[k],对结点 j 和 i 建立一条 j -> i的有向边,边权为a[k],求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路。

问题转换为一个求最短/长路


  • 不等式的统一

对于“A+B<=C”,我们可以转换为“A-(-B)<=C”。

对于“A+B>=C”,我们可以转换为“(-A)-(-B)<=-C”。

对于“A+B<C”与“A+B>C”,可以转换为“A+B<=C-1”与“A+B>=C+1”。

对于“A+B=C”,可以转换为“A+B<=C”与“A+B>=C”。


  • 解的存在与无穷

关于负权:

先来看负权圈的情况,需要求得是X[t] - X[s]的最大值,可以转化成求s到t的最短路,但是路径中出现负权圈,则表示最短路无限小,即不存在最短路。

那么在不等式上的表现即X[t] - X[s] <= T中的T无限小,得出的结论就是 X[t] - X[s]的最大值 不存在。

关于不通:

再来看另一种情况,即从起点s无法到达t的情况,表明X[t]和X[s]之间并没有约束关系。

这种情况下X[t] - X[s]的最大值是无限大,这就表明了X[t]和X[s]的取值有无限多种。

如果我们只需要判断的话,可以建立一个虚点S,到每个点都连一条权值为0的边。不影响最短路的任何关系。


  • 求最小值

我们把权值全部反过来就可以了。

给出的限制条件就是“A+B>=C”一类。

 
 
评论