当前位置: 首页 > >

差分约束系统详解(转化为最短路)

发布时间:

转自:http://www.cnblogs.com/void/archive/2011/08/26/2153928.html




差分约束系统中:



如果求未知数的最大值,那么按小于等于建图后求最短路即可。(因为求最短路是由无穷向下约束而得到的,所以得到的一定是最大值)。


?


如果求未知数的最小值,那么按小于等于建图后求最长路即可。


?


注意所有数据的关系,不能漏掉关系,还有与附加源点的关系。


?


如果是按大于等于建图:


?


求最大值,建图后求最长路;


?


求最小值,建图后求最短路。


?


因为大于等于建图后,相当于未知数都 * -1了,所以求出结果后需要 * -1。




①:对于差分不等式,a - b <= c ,建一条 b 到 a 的权值为 c 的边,求的是最短路,得到的是最大值?
②:对于不等式 a - b >= c ,建一条 b 到 a 的权值为 c 的边,求的是最长路,得到的是最小值?
③:存在负环的话是无解?
④:求不出最短路(dist[ ]没有得到更新)的话是任意解?



一直不知道差分约束是什么类型题目,最*在写最短路问题就顺带看了下,原来就是给出一些形如x-y<=b不等式的约束,问你是否满足有解的问题


好神奇的是这类问题竟然可以转换成图论里的最短路径问题,下面开始详细介绍下


比如给出三个不等式,b-a<=k1,c-b<=k2,c-a<=k3,求出c-a的最大值,我们可以把a,b,c转换成三个点,k1,k2,k3是边上的权,如图



由题我们可以得知,这个有向图中,由题b-a<=k1,c-b<=k2,得出c-a<=k1+k2,因此比较k1+k2和k3的大小,求出最小的就是c-a的最大值了


根据以上的解法,我们可能会猜到求解过程实际就是求从a到c的最短路径,没错的....简单的说就是从a到c沿着某条路径后把所有权值和k求出就是c -a<=k的一个


推广的不等式约束,既然这样,满足题目的肯定是最小的k,也就是从a到c最短距离...


理解了这里之后,想做题还是比较有困难的,因为题目需要变形一下,不能单纯的算..


首先以poj3159为例,这个比较简单,就是给出两个点的最大差,然后让你求1到n的最大差,直接建图后用bellman或者spfa就可以过了


稍微难点的就是poj1364,因为他给出的不等式不是x-y<=k形式,有时候是大于号,这样需要我们去变形一下,并且给出的还是>,<没有等于,都要变形


再有就是poj1201,他要求出的是最长距离,那就要把形式变换成x-y>=k的标准形式


注意点:


1. 如果要求最大值想办法把每个不等式变为标准x-y<=k的形式,然后建立一条从y到x权值为k的边,变得时候注意x-yx-y<=k-1


?? 如果要求最小值的话,变为x-y>=k的标准形式,然后建立一条从y到x的k边,求出最长路径即可


2.如果权值为正,用dj,spfa,bellman都可以,如果为负不能用dj,并且需要判断是否有负环,有的话就不存在








转自:http://www.cnblogs.com/pony1993/archive/2012/09/01/2666996.html





在一个差分约束系统(system of difference constraints)中,线性规划矩阵A的每一行包含一个1和一个-1,A的其他所有元素都为0。因此,由Ax≤b给出的约束条件是m个差分约束集合,其中包含n个未知量,对应的线性规划矩阵A为m行n列。每个约束条件为如下形式的简单线性不等式:xj-xi≤bk。其中1≤i,j≤n,1≤k≤m。


例如,考虑这样一个问题,寻找一个5维向量x=(xi)以满足:






?


这一问题等价于找出未知量xi,i=1,2,…,5,满足下列8个差分约束条件:


x1-x2≤0


x1-x5≤-1


x2-x5≤1


x3-x1≤5


x4-x1≤4


x4-x3≤-1


x5-x3≤-3


x5-x4≤-3


????该问题的一个解为x=(-5,-3,0,-1,-4),另一个解y=(0,2,5,4,1),这2个解是有联系的:y中的每个元素比x中相应的元素大5。


?
引理:设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解,d为任意常数。则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。


?


约束图


???在一个差分约束系统Ax≤b中,m X n的线性规划矩阵A可被看做是n顶点,m条边的图的关联矩阵。对于i=1,2,…,n,图中的每一个顶点vi对应着n个未知量的一个xi。图中的每个有向边对应着关于两个未知量的m个不等式中的一个。


???给定一个差分约束系统Ax≤b,相应的约束图是一个带权有向图G=(V,E),其中V={v0,v1,…,vn},而且E={ (vi,vj) : xj-xi≤bk是一个约束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。引入附加顶点v0是为了保证其他每个顶点均从v0可达。因此,顶点集合V由对应于每个未知量xi的顶点vi和附加的顶点v0组成。边的集合E由对应于每个差分约束条件的边与对应于每个未知量xi的边(v0,vi)构成。如果xj-xi≤bk是一个差分约束,则边(vi,vj)的权w(vi,vj)=bk(注意i和j不能颠倒),从v0出发的每条边的权值均为0。


??
定理:给定一差分约束系统Ax≤b,设G=(V,E)为其相应的约束图。如果G不包含负权回路,那么x=( d(v0,v1) , d(v0,v2) , … , d(v0,vn) )是此系统的一可行解,其中d(v0,vi)是约束图中v0到vi的最短路径(i=1,2,…,n)。如果G包含负权回路,那么此系统不存在可行解。


?


差分约束问题的求解


???由上述定理可知,可以采用Bellman-Ford算法对差分约束问题求解。因为在约束图中,从源点v0到其他所有顶点间均存在边,因此约束图中任何负权回路均从v0可达。如果Bellman-Ford算法返回TRUE,则最短路径权给出了此系统的一个可行解;如果返回FALSE,则差分约束系统无可行解。


???关于n个未知量m个约束条件的一个差分约束系统产生出一个具有n+1个顶点和n+m条边的约束图。因此采用Bellman-Ford算法,可以再O((n+1)(n+m))=O(n^2+nm)时间内将系统解决。此外,可以用SPFA算法进行优化,复杂度为O(km),其中k?为常数。





友情链接: