算法合集之《浅析差分约束系统》.ppt

数与图的完美结合 ------浅析差分约束系统 华中师大一附中 冯威 引言 在面对多种多样的问题时，我们经常会碰到这样的情况：往往我们能够根据题目题面意思来建立一些简单的模型，但却面对这些模型无从下手。这时我们应该意识到，也许能够将这种模型与其他的模型之间搭起一座桥梁，使我们能够用更简单直接的方式解决它。这里我们介绍一种方法，它很好地将某些特殊的不等式组与图相联结，让复杂的问题简单化，将难处理的问题用我们所熟知的方法去解决，它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过zju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用，并逐渐归纳解决这类问题的思考方向。 Bellman ford 算法 算法简单介绍 这个算法能在更一般的情况下解决最短路的问题。 一般在： 1.该算法下边的权值可以为负 2.可以运用该算法求有向图的单元最长路径或者最短路径 . 3. … Bellman ford 算法 松弛技术： 对每一个结点v，逐步减小从起点s到终点v最短路的估计量dist[v]直到其达到真正的最短路径值mindist[v]。 以单元最短路径为例这个操作就是保证 dist[v]=dist[u]+w[u,v]， 即 if dist[v]dist[u]+w[u,v] then dist[v]=dist[u]+w[u,v] 如果是最长路径则是保证 dist[v]=dist[u]+w[u,v] Bellman ford 算法 伪代码如下： For i=1 to |V|G||-1 Do for 每条边(u，v) Do 更新操作（u，v，w（u，v）） For 每条边（u，v） Do if 仍然有可更新内容 then return False Return True Bellman ford 算法 MAX MAX MAX MAX 0 6 7 8 5 -2 -4 -3 7 9 2 S T 6 MAX 7 MAX 0 6 7 8 5 -2 -4 -3 7 9 2 S T 6 4 7 2 0 6 7 8 5 -2 -4 -3 7 9 2 S T 2 4 7 2 0 6 7 8 5 -2 -4 -3 7 9 2 S T 图例中，S为源节点，粗线段覆盖的边表示最近一次执行更新操作的边。算法执行|V|-1次操作，每次操作都对所有可以进行松弛操作的边进行扩展。 Bellman ford 算法 最终状态如下图。 2 4 7 -2 0 6 7 8 5 -2 -4 -3 7 9 2 S T Bellman ford 算法 证明算法的正确性 1．设G=（V，E）为有向加权图，源节点为S，加权函数为w：E-〉R。如果有负权回路则Bellman-ford算法一定会返回布尔值false,否则返回TRUE。 2．设G=（V，E）为有向加权图，源节点为S加权函数为w：E-〉R，并且G不含从s可达的负权回路，则算法Bellman-ford终止时，对所有从s可达的结点v有d[v]=mindist（s，v）。 差分约束系统 对于解决差分约束系统问题的操作过程和使用原理，我们通过下面一道简单的题目进行了解。 引例：Zju1508 Interval 题目大意：有一个序列，题目用n个整数组合 [ai，bi，ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。如果不存在则输出 -1。 差分约束系统 输入：第一行包括一个整数n，表示区间个数，以下n行每行描述这些区间，第i+1行三个整数ai，bi，ci，由空格隔开，其中0=ai=bi=50000 而且 1=ci=bi-ai+1。 输出：一行，输出满足要求的序列的长度的最小值。 差分约束系统 将问题数字化： 定义数组T，若数字i出现在序列中，则Ti=1，否则Ti=0，那么本题约束条件即为 建立不等式模型： 这样的描述使一个约束条件所牵涉的变量太多，不妨设 (i=1,2,…,n) 差分约束系统 约束条件即可用以下不等式表示 值得注意的是，这样定义的S若仅仅满足约束条件的