前言
第一次接触差分约束,对着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[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与点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。