诗歌网站开发意义,叮当小程序制作平台,甘肃找人做网站多少钱,深圳市建网站公司---恢复内容开始--- 转自#xff1a;http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 差分约束系统中#xff1a; 如果求未知数的最大值#xff0c;那么按小于等于建图后求最短路即可。#xff08;因为求最短路是由无穷向下约束而得到的#xff0c;所以得到…---恢复内容开始--- 转自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-yb不等式的约束问你是否满足有解的问题 好神奇的是这类问题竟然可以转换成图论里的最短路径问题下面开始详细介绍下 比如给出三个不等式,b-ak1,c-bk2,c-ak3,求出c-a的最大值,我们可以把a,b,c转换成三个点k1k2k3是边上的权如图 由题我们可以得知这个有向图中由题b-ak1,c-bk2,得出c-ak1k2,因此比较k1k2和k3的大小求出最小的就是c-a的最大值了 根据以上的解法我们可能会猜到求解过程实际就是求从a到c的最短路径没错的....简单的说就是从a到c沿着某条路径后把所有权值和k求出就是c -ak的一个 推广的不等式约束既然这样满足题目的肯定是最小的k也就是从a到c最短距离... 理解了这里之后想做题还是比较有困难的因为题目需要变形一下不能单纯的算.. 首先以poj3159为例,这个比较简单就是给出两个点的最大差然后让你求1到n的最大差直接建图后用bellman或者spfa就可以过了 稍微难点的就是poj1364因为他给出的不等式不是x-yk形式有时候是大于号这样需要我们去变形一下并且给出的还是,没有等于都要变形 再有就是poj1201他要求出的是最长距离那就要把形式变换成x-yk的标准形式 注意点: 1. 如果要求最大值想办法把每个不等式变为标准x-yk的形式,然后建立一条从y到x权值为k的边,变得时候注意x-yk x-yk-1 如果要求最小值的话,变为x-yk的标准形式然后建立一条从y到x的k边求出最长路径即可 2.如果权值为正用djspfabellman都可以如果为负不能用dj并且需要判断是否有负环有的话就不存在 转自http://www.cnblogs.com/pony1993/archive/2012/09/01/2666996.html ---恢复内容结束--- 在一个差分约束系统(system of difference constraints)中线性规划矩阵A的每一行包含一个1和一个-1A的其他所有元素都为0。因此由Ax≤b给出的约束条件是m个差分约束集合其中包含n个未知量对应的线性规划矩阵A为m行n列。每个约束条件为如下形式的简单线性不等式xj-xi≤bk。其中1≤i,j≤n1≤k≤m。 例如考虑这样一个问题寻找一个5维向量x(xi)以满足 这一问题等价于找出未知量xii1,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为任意常数。则xd(x1d,x2d,…,xnd)也是该系统Ax≤b的一个解。 约束图 在一个差分约束系统Ax≤b中m X n的线性规划矩阵A可被看做是n顶点m条边的图的关联矩阵。对于i1,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的最短路径(i1,2,…,n)。如果G包含负权回路那么此系统不存在可行解。 差分约束问题的求解 由上述定理可知可以采用Bellman-Ford算法对差分约束问题求解。因为在约束图中从源点v0到其他所有顶点间均存在边因此约束图中任何负权回路均从v0可达。如果Bellman-Ford算法返回TRUE则最短路径权给出了此系统的一个可行解如果返回FALSE则差分约束系统无可行解。 关于n个未知量m个约束条件的一个差分约束系统产生出一个具有n1个顶点和nm条边的约束图。因此采用Bellman-Ford算法可以再O((n1)(nm))O(n^2nm)时间内将系统解决。此外可以用SPFA算法进行优化复杂度为O(km)其中k 为常数。转载于:https://www.cnblogs.com/xuyanqd/p/8762762.html
