文档介绍：数与图的完美结合
------浅析差分约束系统
华中师大一附中冯威
引言
在面对多种多样的问题时,我们经常会碰到这样的情况:往往我们能够根据题目题面意思来建立一些简单模型,但却面对这些模型无从下手。这时我们应该意识到,也许能够将这种模型与其他的模型之间搭起一座桥梁,使我们能够用更简单直接的方式解决它。这里我们介绍一种方法,它很好地将某些特殊的不等式组与图相联结,让复杂的问题简单化,将难处理的问题用我们所熟知的方法去解决,它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过zju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用,并逐渐归纳解决这类问题的思考方向。
Bellman ford 算法
算法简单介绍
这个算法能在更一般的情况下解决最短路的问题。
一般在:
.
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 算法
证明算法的正确性
=(V,E)为有向加权图,源节点为S,加权函数为w:E-〉R。如果有负权回路则Bellman-ford算法一定会返回布尔值false,否则返回TRUE。
=(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。
输出:一行,输出满足要求的序列的长度的最小值。