差分约束系统

偏执的太偏执、 2021-10-29 13:34 350阅读 0赞

# 差分约束系统 #

前言:在清北学堂模拟赛的差分约束题写炸了，感觉有必要来总结一下差分约束

### 问题模型 ###

--------------------

求解由若干**不等式**限制的一组最大或最小未知数解

## 思想 ##

当我们求解形如**X1-X2<=d**的问题时，我们会发现将式子变化为X1<=X2+d和最短路问题里的**三角不等式**dis\[u\]<=dis\[v\]+w极为相似，故我们可以将不等式组的最值求解问题转化为求解最短路的问题。  
我们求解Xn-X1的最值问题其实等价于以 节点1 为源点，跑**单源最短路**的问题。因为三角不等式的松弛操作是尽量将式子**"取等"**，故当跑最短路时，未知数的值尽可能的大，进而逼近，满足不等式；跑最长路时，未知数的值尽可能的小，进而逼近，满足不等式。故**最短路可用于**求解Xn-X1的**最大值**，而**最长路可用于**求解Xn-X1的**最小值**。

## 例题 ##

### differ(清北学堂) ###

> 这是一道差分约束基础练习题。  
> 给出 m 个约束条件，每个约束条件属于  
> ?? − ?? ≤ ?, ?? − ?? ≥ ?, ?? − ?? = ?  
> 三种形式之一。  
> 给出 Q 个询问，每个询问都为：求?? − ??的最大值  
> (变量数)n<=200 m<=10000 Q<=100000

**解析**：观察数据范围，发现n<=200,故可用**Floyd算法**求解  
 xi-xj=w 可以转化为正反向分别连一条权值的绝对值为w的有向边  
 但需注意判**重边**和dis\[i\]\[j\]为**负数**的情况（说多了都是泪）

--------------------

### \[SCOI2011\] 糖果 ###

**解析**： 差分约束裸题。需要从超级源点向每个点连一条长度为1的有向边，因为每个小朋友都至少分到一个糖果

--------------------

### 小k的农场 ###

**解析**：这道题只需判断是否有解（是否存在负环），故建立超级源点以保证连通性。

--------------------

### 排队布局 ###

**解析**：这道题需要跑两遍spfa，第一遍从超级源点跑，判断是否有解（是否存在负环），第二遍从节点1开始跑一遍单源最短路，如果能够更新到n，则dis\[n\]即为所求，否则若dis\[n\]为Inf（未被更新到），则1号奶牛和N号奶牛之间的距离可以无穷大。

--------------------

### Intervals ###