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

2006年全国信息学冬令营讲座第1页/共21页数与图的完美结合-------浅析差分约束系统华中师大一附中冯威[摘要]在面对多种多样的问题时，我们经常会碰到这样的情况：往往我们能够根据题目题面意思来建立一些简单的模型，但却面对这些模型无从下手。这时我们应该意识到，也许能够将这种模型与其他的模型之间搭起一座桥梁，使我们能够用更简单直接的方式解决它。这里我们介绍一种方法，它很好地将某些特殊的不等式组与图相联结，让复杂的问题简单化，将难处理的问题用我们所熟知的方法去解决，它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过zju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用，并逐渐归纳解决这类问题的思考方向。[目录]◆关键字·······························································································【2】◆Bellman-ford算法············································································【2】◇算法简单介绍·················································································【2】◇算法具体流程················································································【2】◇例题一ZJU2008··············································································【4】◆差分约束系统····················································································【5】◇例题二ZJU1508··············································································【5】◇线性程序设计·················································································【7】◇差分约束系统·················································································【7】◇例题三ZJU1420············································································【8】◆结语···································································································【9】◆附录···································································································【9】2006年全国信息学冬令营讲座第2页/共21页[关键字]差分约束系统、不等式、单元最短路径、转化[正文]在分析差分约束系统之前，我们首先介绍一个解决单元最短路径问题的BellmanFord算法，它的应用十分广泛，在差分约束系统中更充当着重要的角色。Bellman-ford算法算法简单介绍这个算法能在更一般的情况下解决最短路的问题。何谓一般，一般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。我们这里仅以最短路径为例。Bellmanford类似于Dijkstra算法，对每一个节点vV，逐步减小从起点s到终点v最短路的估计量dist[v]直到其达到真正的最短路径值mindist[v]。Bellman-ford算法同时返回一个布尔值，如果不存在从源结点可达的负权回路，算法返回布尔值TRUE，反之返回FALSE。算法具体流程1．枚举每条边(u,v)E（G）。2．对枚举到的边进行一次更新操作。3．回到步骤1，此过程重复n-1次，以确定没有更可以优化的情况。4．枚举每条边（u，v）若仍然存在可以更新的边，则说明有向图中出现了负权回路，于是返回布尔值FALSE。5．返回布尔值TRUE。注：这里的更新操作是一种松弛技术，以单元最短路径为例这个操作就是保证dist[v]=dist[u]+w[u,v]，即ifdist[v]dist[u]+w[u,v]thendist[v]=dist[u]+w[u,v]，如果是最长路径则是保证dist[v]=dist[u]+w[u,v]。定义一个有向图G=（V，E），w（u，v）表示由结点u到v的边的权值。伪代码如下：Fori=1to|V|G||-1Dofor每条边(u，v)E|G|Do更新操作（u，v，w（u，v））For每条边（u，v）E|G|Doif仍然有可更新内容thenreturnFalseReturnTrue2006年全国信息学冬令营讲座第3页/共21页下图描述了该算法的操作过程，粗线条代表已更新线段图例中，S为源节点，粗线断覆盖的边表示最近一次执行更新操作的边。算法执行|V|-1次操作，每次操作都对所有可以进行松弛操作的边进行扩展。证明一下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）。证明：设v为从s可达的节点，且p=v0,v1,..,vk为从s到v的一条最短路径，其中v0=s，vk=v。因为路径p是简单路径，所以k=|V|-1。我们希望通过归纳证明对i=0,1,…,k，在对G的边进行完第i趟操作后有d[vi]=mindist(s,vi),且该等式此后一直保持成立，因为总共有|V|-1次操作，所以上述结论证明命题成立。MAXMAXMAXMAX06785-2-4-3792ST647206785-2-4-3792ST6MAX7MAX06785-2-4-3792ST247206785-2-4-3792ST247-206785-2-4-3792ST2006年全国信息学冬令营讲座第4页/共21页我们发现与Dijkstra不同，Bellmanford更多的是对边进行操作，在稀疏图，即点多边少的图中，用BellmanFord更能高效的解决单元最短路径问题。下面一道例题来进一步熟悉BellmanFord并与Dijkstra作一下简单的时间上的比较。例题一：ZJU2008InvitationCards[题目大意]在有向加权图中G（V，E），邮局要从起点S向其他n个节点发送邮件，于是派出n个邮递员，分别到达其他n个地点发送，然后回到起点S，求出所有邮递员所经过的总路程的最小值。[数据范围]1=P,Q=1000000。P表示节点数目，Q表示边的个数。[题目分析]这道题算法很简单，即求出从s到任意点的最短路径，求其和ANS1，再将所有有向边反向（这个过程将求从另外n个结点到s的最短路径转化为从s到其他n个点的最短路径），再求一次s到任意点的最短路径，求其和ANS2，Ans=Ans1+Ans2即为所求。但是，此题难在数据量上，无论是Dijkstra的O(2V)的算法，还是Bellmanford的O(VE)的算法都无法在数据规模最大的情况下在5s的时间内得出结果，于是需要做出一点优化。关于Dijkstra的优化：用堆维护使寻找需要扩展的点的过程复杂度降低为1。复杂度大幅降低。关于Bellmanford的优化：可以将Bellmanford需要扩展的点放进队列中，扩展顺序有了新的变化。用一个队列queue表示需要更新的点，每次取队列头指针fp所指的点u，搜索所有的边(u,v)属于E，如果dist[u]+w[u,v]比dist[v]更优则更新dist[v]，尾指针rp后挪一位，将v点加入队列queue。这样的优化避免了很多重复的操作，事实证明它的效率仅次于Dijkstra+heap的效率。下面用3种不同的方法来解这道题目，看看结果如何。我们用以下三种方法求最短路径:1．Dijkstra2．BellmanFord3．Dijkstra&Heap在ZJUOnlineJudge中进行评测结果如下：算法运行所有数据所用时间Dijkstra〉5s（TLE）BellmanFord1.46sDijkstra&Heap1.24s差分约束系统对于解决差分约束系统问题的操作过程和使用原理，我们通过下面一道简单的题目进行了解。引例：[例题二]Zju1508Interval2006年全国信息学冬令营讲座第5页/共21页题目大意：有一个序列，题目用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。输出：一行，输出满足要求的序列的长度的最小值。[浅析]初看此题感觉无从下手，我们将范围和个数进行量化，让问题看起来更加简单些。将问题数字化：若记，不存在于序列中如果存在于序列之中如果i0i1{ti那么本题约束条件即为n)1,2,...,(ictibajjii建立不等式模型：这样的描述使一个约束条件所牵涉的变量太多，不妨设i1jjitS(i=1,2,…,n)约束条件即可用以下不等式表示：)n,...,2,1i(cSSi1abii值得注意的是，这样定义的S若仅仅满足约束条件的要求是不能完整体现它的意义的，S中的各个组成之间并不是相对独立的，他们存在着联系。由于i1jjitS，且t要么为1，要么为0，则iS一定比1-iS大，且至多大1。于是有：)n,...,2,1i(1SS)n,...,2,1i(0SSi1-i1ii那么如何找到满足要求的这样一组S，且使其个数最少呢？这里我们看到最少就会联想到贪心，确实这道题目用贪心可行，且不失为一种很好的做法，但在这里我们不作多的介绍。我们将针对这个不等式组进行联想，迁移。注意到不等式中只涉及到了2个未知数，用减号相连接。这样的式子是否与过去曾经学过的Bellmanford中的松弛操作所达到的效果相类似呢？联想：我们需要寻找一个满足以下要求的S数组2006年全国信息学冬令营讲座第6页/共21页)n,...,2,1i(1SS)n,...,2,1i(0SS)n,...,2,1i(cSSi1-i1iii1abii而Bellman-Ford每次的更新操作为v]w[u,d[u]d[v]thend[v]v]w[u,d[u]If即在经过若干次更新操作将要保证d[v]=d[u]+w[u,v]这里我们也有一个已知量-----边的权值，即w[u,v]，于是整理一下得d[u]-d[v]=w[u,v]经过这样的变形，不难看出，两个式子有着极为惊人的相似！于是做出如下的转化：1．我们将n10S,...,S,S，看作n+1