差分约束自学笔记

先鸽着。（拖延症）其实是寒假中旬学的。

这个真鸽的太久了。。现在是2.13了。
差分约束解决的是不等式类型的题目。
运用SPFA来以期望优秀的时间跑出答案。
由于鸽的有点久了，今天先大概谈谈。
首先，要纠正一下思维。
这里的SPFA绝非是为了优解，而是为了满足约束。
差分约束吗，就是通过SPFA来约束解。
至于要求最优的解则是通过建图体现。
至于对付最短路f[i]的含义也要弄清楚。
（一般有两种设法：i的值，1~i的前缀和，具体后面整理）
因为在赋初始值，对于起点等都要求把我准确。
个人认为有考逻辑性。
当然，今天只能泛泛而谈，具体等明天复习了再说。

今天终于过了模板。（不要问我为什么模板都过不掉）
首先先是前缀和类型。
如洛谷P1250种树。这题就是典型的维护前缀和。
而像P1993，P3275及模板就都是针对于个体关系了。
这就需要把不等关系提炼了。
如不等式:\(i-j \le x\)
那么就把转换：\(j \ge i-x\)
如此就可以通过连边了。（或者\(i \le j+x\)）
如果等于的话连两条权为0的边。
其它的特殊关系也一次类推。
至于为什吗\(j \ge i-x\)只用连单向的边就行了呢？
因为一开始，我们通过虚点0的方式，已将每个点都遍历了。每个关系初步都成立了。
假设一条边是从\(i->j\)的，那么假设i变了，那么j就会由边遍历到，也会被约束。
而如果j变了，则可以理解为j被约束的更紧了（因为统一都是求最长路或最短路）
如此，只需连接一条即可。当然，连边的方式决定最长路还是最短路。
那为什么等于要连两条边？因为无论i还是j变了，另一个都要变。

好了，下面是细节注意。
首先是我一再要注意的含义。
一定要知道含义，不能因为平常最短路的f[i]意义而迷惑。
这里是约束，求最长路反而求的是最小解，反之亦然。
然后是开数组要注意0与其它点的边。
对于虚点0一定要注意，它的目的是让SPFA跑起来。也防止图不连通。
还有就是负环问题，这个我发现大家意见不统一，但我要明白，要有自己的方式。
因为抛去含义，还是最短/长路，所以有如下性质

• 每个点最多被松弛(n-1)次，因为每次松弛必由新的点引起。
• 最短/长的路径上点的个数不会超过全图点的个数。
• 最优子结构性质。（恰似DP，这里是复习作用）
  这样，两种判负环方式就没有歧义了。当然判负环还是要注意的。