算法与acm

差分约束系统

2008年11月28日 阅读(58)

转载请注明作者:phylips@bmy  出处:http://duanple.blog.163.com/blog/static/709717672008102885325526/

poj 1275 3159 1364 1716 1201 3169
这类问题,就像网络流,图论,dp,关键在列出满足的表达式,建立好数学模型,剩下的过程就很简单了。所以主要难点在于构图,从实际的描述抽象成模型。准确找到约束条件。

关于基础知识可以查看clrs 22.4节。下面只介绍我遇到的一些问题和理解。

所谓的差分约束系统,实际上指一系列的表达式,满足 形如{ xi – xj <= a}
求解实际上转化成了图论里的一个等价问题,最短路问题,实际上巧妙的利用了最短路具有的性质 di – dj <= w(j,i)
如果这样的最短路求成来了,他们的值便可以直接作为xi xj的一组可行解。

图论里求最短路,有很多方法,差分约束系统,一般利用的是单源最短路,而在单源最短路算法中,常见的是dijkstra和bellman-ford算法。这两个算法各有优劣。

dijkstra算法,效率比较高,如果用堆实现,可以达到O(vlogv+E)的复杂度,但是它只能解决正边权类型的问题,对于负边权的问题,必须采用bellman-ford算法,它的复杂度是VE.

bellman-ford算法很强大,不单可以求最短路,还可以求最长路。一般如果约束条件是 <=形式的,就标志着要求最短路,>=则要通过求最长路解决。
当然这两种约束是可以转化的,因为 xi – xj <= a实际上等价于xj- xi >= a。

一.优化途径:
1.如果改变边的松弛(relax)顺序,程序的执行顺序会有很多改观
2.当所有边都不能再松弛的时候,便可以跳出循环了,不必全部循环V-1次
这些可以通过poj1716 1201体验到
二.关于Dist[]的初始化化
1.如果将源点到各点的距离初始化为0,最终求出的最短路满足 它们之间相互最接近了
2.如果将源点到各点的距离初始化为INF(无穷大),其中之1为0,最终求出的最短路满足 它们与该点之间相互差值最大。
这些可以从poj3169 layout 得到证实。
三.
关于dikstra算法的堆实现,有两种策略,一种是一开始把全部节点放到堆里,为每个节点维护一个在堆里的索引数组。另一种策略是当当前点被更新才放到堆里,但是要注意标记已经求得最短路的哪些点,避免重复求值。
我采用的是第一种策略,去求解的poj3159 Candies

当然还有一个优化是,如果已经找到了目标点,就可以退出了,不必全部求出最短路

四.陷阱
int a[MAX] =  {INF};
注意a里面的元素只有第一个会被赋为INF,其他会被赋为0,而不是INF。

关于模型的建立,其实,很多情况下我们的 xi都是一个和式,比如从开头到现在的某个量的积累值,比如poj1716 1201中,我们要定义x[i]为点集里小于i的数的个数,则x[j] – x[i]则表示了落在线段区间[i,j]的点的个数。还有poj1364 King 也是类似,另外一些可能就是比较简单的直接的约束关系。

比较复杂的如poj1275 Cashier Employment
这个问题比较特殊,乍看其他上述问题都是寻找最小数目的点,使这些点可以覆盖线段。而这个则是找一些数目的人,而人实际上是一些线段,使这些线段可以在那些特点的总数目可以满足要求并且数目最少。关键在定义一个状态,这里如果大胆定义i时刻出纳员数目s[i],就可以了,然后利用这个s[i]便可以找到所有的约束关系,并列出不等式,这样模型就建立好了。

这个可以参考刘汝佳的书P307,图论最短路那部分,刚好以这个问题为例,而且这个问题求的就是最长路。对于sum可以二分进行优化,不过我直接穷举也过了。

poj3159 Candies
这是我接触差分约束的第一题。设S[a]为kid a获得的candies数,则每一行代表的约束是S[b]-S[a]<=c,目标函数是使得S=S[N]-S[1]最大。
利用差分约束的思想建图,对于每一条约束,从a向b做一条长为c的边,则从1到N的最短路即为所求。由于本题c皆为非负数,所以可以用Dijkstra高效解决。

You Might Also Like