差分约束图解
差分约束主要解决问题
1.求不等式的可行解
原点需要满足的条件:从 源点 出发，一定可以走到所有的边。
步骤:
1.现将每个不等式 \(x_i \leq x_j+c_k\) ,转化为一条从\(x_j\)走到\(x_i\)，长度为\(c_k\)的一条边
2.找一个 超级源点 ，使得该源点一定可以 遍历所有边 。
3.从源点求一边单源最短路
结果1:如果 存在负环，则原不等式组一定 无解
结果2:如果 没有负环，则dist[i]就是原不等式组的 可行解
2.如何求 最大值 或 最小值
结论:如果求的是 最小值，则应该求 最长路 ，不等式组的符号列成 \(\geq\)
如果求的是 最大值，则应该求 最短路 ，不等式组的符号列成 \(\leq\)
问题:如何转化\(x_i \leq c\),其中c是一个常数，这类的不等式
方法:建立一个 超级源点0，然后建立0->i长度是c的边即可
以求\(x_i\)的最大值为例:
求从所有从\(x_i\)出发，构成的不等式链:
\(x_i \leq x_j+c_1 \leq xk+c2+c1 \leq ... \leq c_1+c_2+c_3+...\)
所计算出的上界，最终\(x_i\)的最大值等于所有上界的最小值
这里所有上界的最小值可以理解这么一个例子:
则满足限制的\(x_i\leq5\)。当我们要求\(x_i\)所能满足的最大值时，要先满足这些全部的限制，那当然是先取得上界的最小值，才能知道能取到的最大\(x_i\),所以我们需要跑一个最短路算法
同理，我们来理解一下最小值，这是一个完全相反的过程。求该不等式链的下界的最大值。
\(x_i \geq x_j+c_1 \geq xk+c2+c1 \geq ... \geq c_1+c_2+c_3+...\)
与上同理，我们要取到最大值，所以要求到下届的最大值，用最长路算法
经验
写了几道题的感受
1.差分约束题目的一些特征:拥有大量的不等关系，且这些不等关系是有联系的。
2.一些小细节:
1.要确认时算的最大值还是最小值，确定不等号方向，这样能确定跑最长路还是最短路。
2.一定要记得超级源点，很关键，确定了超级源点，才能确定最开始放入队列的元素。
3.还有一定要找到边界，就是一个未知量大于一个准确值，这样我们就找到了，该未知量和边界的情况，从而递归得到，上下界。