对于差分约束系统的一些理解

时间：2015-08-08 15:00:34 阅读：229 评论：0 收藏：0 [点我收藏+]

【1】最短路如何建图？
差分约束系统是{di-dj<=u}的集合，
考虑将di-dj<=u变形为dj+u>=di，
∴结点i要满足所有的结点j的dj+u>=di，
那么必须至少取到min(dj+u)，如果取得更大，就会矛盾。
于是这样就可以建最短路，求出一组取值。

【2】这组取值有什么意义？
它通过最短路得到。
刚好满足了所有条件，约束得最紧密。
也就是说，它不唯一，任意的di可能可以更小，相对差就会变大。

【2】这组取值的一个性质：可以平移
简略的证明：∵dj+u>=di，设dj‘=dj+a，∴dj+a+u>=di+a即dj‘+u>=di‘.

【3】松弛操作次数上限为n-1。
描述性证明：最短路径最多有n-1条边。迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程，最短路径树最多n-1层。

【4】结点初始取值
设虚拟结点0，从0到任意结点i连一条边，设其权值为0，然后做最短路。
现在问题来了：为什么这样是成立的？
上网找什么资料都不讲究正确性，直接给出做法。
现在其实是多给了n组d0+0>=di的不等式，要证明加了这么多组和没加这些的解的存在性不受改变。
∵出现矛盾只能是出现了负权回路。
∴即证明通过加了0结点出现了负权回路。
由于0只连出去，不连回来，∴负权回路上必然没有0结点。
∴假如现在有负权回路，那么原来一定也有负权回路。
不过注意，加了0的限制条件，所得到的解就不一定是最优解了。

例如，对于差分约束系统d1-d2>=-3。
首先建立结点1，2，建边(1,2,3)。
然后建立结点0，连接(0,1,0),(0,2,0)。
求出的值d1=d2=0。

【5】如何求出一组最小正整数解（非负整数解，etc.）
每个联通块是互相约束的。
先用并查集求联通块，然后每块平移。

对于差分约束系统的一些理解

原文：http://blog.csdn.net/u013598409/article/details/47357933

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)