差分约束系统（附习题洛谷P1250&P2294&P3275）

Swing_YL · 2018-10-14 19:44:00 · 个人记录

差分约束系统

差分约束是用图论中的最短路解决一些不等式(组)。

请求出一组满足： $X1-X5 <= 1

X1 - X3 <= 3

X2 - X4 <= -2

的长度为5的序列

怎么建图？拿第一个式子来说，X1-X5 <= 1 (X1<= X5+1), 就从结点5向结点1连一条权为1的边.

因为最短路的性质：Dis(i) <= Dis(j) + edge(j, i).

为了图的连通性最后再新建一个超级源，连到每个结点，长度是0

（即Xi<=X0+0，因为X0不是题目中的结点，所以随意约定它的值不会影响答案）

从超级源跑单源最短路，满足这一系列不等式的的序列就是最后的Dis(1) 到 Dis(n)

如果是 Xi - Xj >= Wk 的话，两边乘以-1，转换成Xj - Xi <= -Wk

所以最后的方法是：i到j连一条权为-Wk的边.

如果路径中出现负环，就表示最短路可以无限小，即不存在最短路，那么在不等式上的表现即X[n] - X[0] <= T中的T无限小，得出的结论就是X[n] - X[0]的最大值不存在。

这种情况表明X[n]和X[0]之间没有约束关系，X[n] - X[0]的最大值无限大，即X[n]和X[0]的取值有无限多种。在代码实现过程中体现为dis[n]=INF。

如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路.(即求所有满足条件里的最小的)

相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成">="，建图后求最长路。（即要求所有的最小值都满足）

[l, r]$至少要种T棵树可以转换为$Sum(r) - Sum(l-1) >= T

转换完，就可以用上面的方法求解了：

先乘-1，转换成Sum(l-1) - Sum(r) <= -T

还有两个条件，即：

Sum(i) - Sum(i-1) <= 1

即每个位置最多种一棵树

Sum(i-1) - Sum(i) <= 0

差分约束规定的只是元素的相对关系，按照题意相对关系不变时最后的答案尽可能小，所以让dis[]一起减去他们中的最小值，得到最少种的树，dis[n]即为答案。

题目中给定[l,r]=w,相当于

Sum(r) - Sum(l-1) <= w

Sum(r) - Sum(l-1) >= w

则同时从l-1到r连边权为w的边，从r到l-1连边权为-w的边。

题目要求判断是否成立，即判断是否有环。

题目要求每个小孩至少有一个糖果，所以从超级源到每个点连一条边权为1的边。

然后就按照题目给的方式式子就行。

无解就是有环。

两个要注意的点：

1.宽搜超时了一个点，改深搜更新最长路同时判环。

2.特殊数据卡一个点：从超级源向外连边时，倒着：

for(LL i=n;i>=1;i--)
   add(0,i,1);

意思是有可能环在最后，而先走完前边才能搜到环，倒着加边，就可以一上来就搜到环（这个只与数据有关，不用特别在意，毕竟听说差分约束不是这个题的正解）。