差分约束学习笔记

差分约束可以分为求最大值或最小值;

1. 求最大值:

形如求 f[n]-f[0] 的最大值,那么该式肯定有一个上界 ,那么我们就需要列出形如 xi-xj<=d (连一条 j -> i 的边权为 d 的边)的方程组,又因为在对式子取最大值时,我们所取的那个上界肯定是最小的那一个,所以是在建好了的图上跑最短路;

2.求最小值:

形如求 f[n]-f[0] 的最小值,那么该式肯定有一个下界 ,那么我们就需要列出形如 xi-xj>=d (连一条 j -> i 的边权为 d的边)的方程组,又因为在对式子取最小值时,我们所取的那个下界肯定是最大的那一个,所以实在建好了的图上跑最长路;

3、对于题目所给的不等式组的转化

做题时可能会遇到不等式中的符号不相同的情况,但我们可以对它们进行适当的转化

(1)方程给出:X[n-1]-X[0]>=T ,可以进行移项转化为: X[0]-X[n-1]<=-T。

(2)方程给出:X[n-1]-X[0]<T, 可以转化为X[n-1]-X[0]<=T-1。

(3)方程给出:X[n-1]-X[0]=T,可以转化为X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T,再利用(1)进行转化即可

原文地址:https://www.cnblogs.com/nnezgy/p/11718051.html