算法总结差分约束系统.doc

Contents一、 定义二、详解三、例题一、 定义（百度百科）：如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi=bk(i,j1,n,k1,m),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。观察xj-xi=bk，会发现它类似最短路中的三角不等式dv=du+wu,v，即dv-du=wu,v。因此，以每个变量xi为结点，对于约束条件xj-xi=bk，连接一条边(i,j)，边权为bk。我们再增加一个源点s,s与所有定点相连，边权均为0。对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终d i即为一组可行解。例如，考虑这样一个问题，寻找一个5维向量x=(xi)以满足：这一问题等价于找出未知量xi，i=1,2,5，满足下列8个差分约束条件：x1-x20x1-x5-1x2-x51x3-x15x4-x14x4-x3-1x5-x3-3x5-x4-3该问题的一个解为x=(-5,-3,0,-1,-4)，另一个解y=(0,2,5,4,1)，这2个解是有联系的：y中的每个元素比x中相应的元素大5。引理：设x=(x1,x2,xn)是差分约束系统Axb的一个解，d为任意常数。则x+d=(x1+d,x2+d,xn+d)也是该系统Axb的一个解。bellman-ford算法伪代码：for each v V do dv - 无限大; ds - 0Relaxationfor i =1,.,|V|-1 dofor each edge (u,v) 属于 E dodv du + w(u,v) then no solution在实际的应用中，一般使用SPFA(Shortest Path Fast Algorithm)算法来实现。差分约束系统中源点到每个点的距离确定关于Dist的初始化化1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。3.差分约束系统的确立要根据自己确定的约束条件，从约束点走向被约束点连边一般有两种方法，第一种是连边后求最长路的方法，第二种是连边后求最短路的方法。例：dx-dy=Z如果想连边后求最长路 那么将不等式变形为这种形式 dx=dy+z y-x连一条权值为z的边求最短路则变形成dy=dx-z x-y连一条权值为-z的边。如果是别的不等式，也可以根据情况变形。但是要保证的是 两个变量（x,y)的系数一定要是正的。而常量则不一定。定理：将如上差分约束系统转换成图后，以为源点得到的最短路径序列为（如果有解），则满足且若为任意解，则有。证明：首先由，则显然有满足，这是因为每条边对应一个不等式且由图的构造法可知。其次考察到的最短路径，我们有与直接相连且由路径最短知，其中为不等式的常量即为边的权，所以有。对k做归纳，由，又，所以即所以后者成立。证毕例：设有n个盒子标号为1.n，每个盒子最多放1个球。放法满足（0im）约束，其中表示区间最多可放个球，求这n个盒子最多可放多少个球。1令前k个盒子放的数目为，则有，（1 in），（1 im）。以此约束条件用如上算法给出最短路径序列，由定理知是合法的放法，且为最大值。二、详解引自某网友：（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：X1 - X2 = 0X1 - X5 = -1X2 - X5 = 1X3 - X1 = 5X4 - X1 = 4X4 - X3 = -1X5 - X3 = -3X5 - X4 v，都有：d(v) v的权值。 显然以上不等式就是d(v) - d(u) = w(u, v)。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图，每个未知数Xi对应图中的一个顶点Vi，把所有不等式都化成图中的一条边。对于不等式Xi - Xj = c，把它化成三角形不等式：Xi Vi，权值为c。最后，我们在这张图上求一次单源最短路径，这些三角形不等式就会全部都满足了，因为它是最短路径问题的基本性质嘛。 话说回来，所谓单源最短路径，当然要有一个源点，然后再求这个源点到其他所有点的最短路径。那么源点在哪呢？我们不妨自已造一个。以上面的不等式组为例，我们就再新加一个未知数X0。然后对原来的每个未知数都对X0随便加一个不等式（这个不等式当然也要和其它不等式形式相同，即两个未知数的差小于等于某个常数）。我们索性就全都写成Xn - X0 = 0，于是这个差分约束系统中就多出了下列不等式：X1 - X0 = 0X2 - X0 = 0X3 - X0 = 0X4 - X0 = 0X5 - X0 = d(u) + w(u, v)也就是 d(v) - d(u) = w(u, v) 所以建图的时候要先把所有不等式化成大于等于号的。其它各种过程，包括证明为什么解出的是最小值的证法，都完全类似。 用到差分约束系统的题目有ZJU 2770，祝好运。三、例题POJ-1201Intervals 基础的差分约束：题目大意：给出N个整数区间ai,bi，并且给出一个约束ci，（ 1= ci = ci个，求出数组Z的最小长度。分析：对于给定的条件，假设Sj为数组Z在0,j上的包含的元素个数，则我们可以根据条件得到Sbi+1 - Sai = ci = Sai - Sbi+1 = Sj+1-Sj = 0，可以得到一个差分约束系统。但是题目要求我们的是求约束图的最长路径，则我们应该反过来做，令SN = 0，从终点开始求。 若要满足不等式V(a)=V(b)+W(b,a),则可以从b到a连一条权为W(b,a)的边,求最短路得之。从b到a的最短路意味着满足所有不等式的a-b之最大值。即a-b=-w,所有-w就是所求的ansCODE：cppview plaincopy1. /*差分约束*/2. /*AC代码：375ms*/3. #include4. #defineMAXN500055. #defineINF0x7fffffff6. usingnamespacestd;7. structedge8. 9. intto,w,next;10. E3*MAXN;11. intheadMAXN,ecnt;12. intStackMAXN,disMAXN,cntMAXN;13. boolInstackMAXN;14. intN,top,l,r;15. voidInsert(intfrom,intto,intw)16. 17. Eecnt.to=to;18. Eecnt.w=w;19. Eecnt.next=headfrom;20. headfrom=ecnt+;21. 22. boolRelax(intfrom,intto,intw)23. 24. if(distodisfrom+w)25. 26. disto=disfrom+w;27. returntrue;28. 29. returnfalse;30. 31. voidInit()32. 33. inti,u,v,w;34. memset(head,-1,sizeof(head);ecnt=0;35. l=INF;r=-INF;36. /Su-Sv+1=-w37. for(i=1;i=N;i+)38. 39. scanf(%d%d%d,&u,&v,&w);40. if(ur)r=v+1;42. Insert(v+1,u,-w);43. 44. for(i=l;ir;i+)45. 46. Insert(i+1,i,0);/Si-Si+1=047. Insert(i,i+1,1);/Si+1-Si=148. 49. 50. voidSPFA(ints,inte)51. 52. inti,u,v;53. top=0;54. memset(Instack,false,sizeof(Instack);55. for(i=s;i=e;i+)56. disi=INF;57. dise=0;/注意要从e开始58. Stack+top=e;59. Instacke=true;60. while(top)61. 62. u=Stacktop-;63. Instacku=false;/出栈64. for(i=headu;i!=-1;i=Ei.next)65. 66. v=Ei.to;67. if(Relax(u,v,Ei.w)&!Instackv)68. 69. Instackv=true;70. Stack+top=v;71. 72. 73. 74. 75. intmain()76. 77. while(scanf(%d,&N)!=EOF)78. 79. Init();80. SPFA(l,r);81. printf(%dn,-disl);/必有解，无需判负环82. 83. return0;84.