关于差分约束系统

前言

　　第一次接触差分约束，对着WC2006的课件以及一堆博客看了一个下午总算明白得差不多了。以前听说过这个，一直觉得是很难、很高深的算法，学了之后发现它确实很高深，但不是很难。还挺好懂……我居然看了一下午哎←_←

前置技能

• 前向星。
• 最短路（最好用bellman-ford或spfa）。
• 不等式。

正文

前向星

↓不会的话看链接咯
前向星

Bellman-ford算法

↓不会的话看链接咯
Bellmanford

spfa

↓不会的话看链接咯
spfa

差分约束系统

　　终于到重点了233。

引例1

题目大意

　　给定n个变量及m个不等式，每个不等式形如x[i]-x[j]<=a[k]（a[k]已知，0<i,j<=n，0<k<=m），求x[n-1]-x[0]的最大值。

简单的例子

　　对于以下给出的n=4,m=5的不等式组

x[3]-x[1]<=2
x[2]-x[1]<=3
x[3]-x[2]<=3
x[4]-x[2]<=6
x[4]-x[3]<=5

　　我们要求x[4]-x[1]的最大值。
　　首先我们运用数学方法，经过一堆加加减减，发现x[4]-x[1]<=min{9,7,11}，于是我们就可以得出，x[4]-x[1]的最大值为7。再确认一遍，没有问题。
　　但是这些怎么交给计算机呢？
————————分割线————————

解答

　　我们重新观察一下不等式的一般情况，x[i]-x[j]>=a[k]，移项，x[i]<=x[j]+a[k]，令a[k]=w[i][j]，那么就是x[i]<=x[j]+w[i][j]，这不就联想到求最短路过程中的松弛操作嘛！因此我们可以将每一个不等式x[i]-x[j]<=a[k]转换为有向图中的一条j->i的权值为a[k]的有向边。
　　建图如下：

　　剩下的就是求点1到点4的最短路了。这时候Bellman-ford或spfa算法就派上用场了。
　　以上的引例就是一个裸的差分约束，而关于这个转化的正确性很好证明，因此（其实是我懒）此处略去。

关于解的存在性问题

1. 求最短路时经过负环，由于求最短路的时候可以无限地在负环上循环，那么这个最短路的值就是无限小，即最短路不存在，因此无解。
2. 点1与点n不连通，则表明x[n]与x[1]不存在约束关系，因此有无数个解。

综上，差分约束问题的解有三种情况：

• 有且只有一个解。
• 无解。
• 有无数个解。

最大值=>最小值

　　有时候我们遇到的是给出m个形如x[i]-x[j]>=a[k]的不等式，要求求x[n]-x[1]的最小值的问题，那么其实和求最大值的情况一样，转化为图的问题。建图过程也是一样，只不过把求最短路变为求最长路。关于解的存在性问题也是类似的。

常见问题及解决方案

　　有时候给出的不等式既有>=也有<=，直接做会有麻烦。于是这时候我们首先要关注问题要求的是最大值还是最小值，如果是最大值的话通过两边同时乘-1的方法将存在>=的不等式的不等号反向，然后进行建图的操作；如果是最小值则反之。
　　还有时候会出现等号，如A-B=C，那么就需要将它转化为A-B>=C和A-B<=C两个不等式，再根据需要将其中一个反向（其实就是在AB两点之间连一条权值为C的双向边）。
　　以及，如果权值都是在整数域上的，如果出现不带等号的不等式，如A-B>C，那么直接转化为A-B>=C+1即可，以此类推。
　　以后有遇到其他的再补充

最基本的差分约束就这么讲完了唔。

差分约束经典应用

先坑着

参考资料

　　网上的一大堆博客都被我借鉴了233。