差分约束系统专题 && 对差分约束系统的理解

具体能解决的问题:

求最长路,最短路,或者判断解是否存在。

在建边的时候:

一般是给你区间减法的关系,或者是这个点到另一个点的关系。如果给你的关系是除法的话,我们可以通过使用两边同时取log的方式,将除法变成两个式子的减法,这样就转换成了减法的建边。

判断最优解的时候:

一般是判断是否有负环或者正环,但是一个spfa只能判断一种,因为正环和负环的松弛条件是不同的,在判断是正环还是负环的时候,一般是判断某一个点的入队次数是不是大于总的点数,如果存在这种情况那肯定是存在正环或者负环的,如果是tle的话,可以考虑(仅供考虑)的一种优化的判断,判断某一个点的入队次数是不是大于sqrt(总的点数)。

对建边的初步理解:

1,如果是求最长路或者最短路的话,我们可以将所有的不等式都化成如下的式子,posA-posB<=d。

然后对于求最长路,就是在spfa的基础上改就可以了。将dis输出初始化成-inf,然后判断条件变成if(dis[ed]<dis[st]+edge[i],cost),这样的时候再去更新。

如果是求最短路的话,松弛条件改一下就可以了。

然后再就是建边的时候,有两种方法(超级源点的建立)。

第一种,如果是求前缀的话,对于posA-posB<=d,我们可以addedge(A,B,d)。这样话,就相当于从大的方向去链接小的方向,注意,如果只是按照题目条件去建边的话,整个图可能是不连通的,为了使图联通,我们可以建立一个超级源点,如果是从大的方向向小的方向建边的话,我们可以使超级源点是(总点数+1),然后这个超级源点再去连其他所有的点,边权为0,这样就不会影响到图,并且能够保证整个图是联通的。

第二种,如果是求后缀的话,我们就可以按照第一种的方法反着来就行了。

但是建边的额时候还是尽量少建点边,很可能会超时。

判断可行解:

对于区间的可行解的话,我们可以直接从右边界遍历到右边界,如果可以的话,判断两个相邻的点的dis(一般间隔是1)是不是变了没如果变了就说明当前这个点肯定有解。

上一篇:【转】WriteMessage的信息在AutoCAD中命令行中实时显示


下一篇:怎样使用 RMAN 增量备份恢复 data guard log gap(日志断档)