差分约束思想及注意事项
发布时间 2023-07-10 20:45:37作者: 铃狐sama
前情提要：晚自习前把老师布置的作业搞完了
但我晚自习总不能和铃兰贴贴吧，所以决定学点新东西
woc你看人家新高一都把差分约束学了
人家周考直接乱杀，但我呢，我只能开摆
差分约束小总结：
如果要求最大值，则想办法把每个不等式变为标准xi-xj<=val(约束）的形式，然后建立一条从 j到i权值为val 的边，最后求最短路径即可。
如果要求最小值，则想办法把每个不等式变为标准 xi-xj>=val的形式，然后建立一条从j到i权值为val的边，最后求最长路径即可。
求路径方法：再增加一个源点s,s与所有定点相连，边权均为0，最终d[ i]的集合就是一组可行解
为了好记：求最值反着约束，反着连边，反着求路径
例如：求最小，约束>=,连边j,i,找最长路
其实记住这些就好了，至于原理......
爬！
做题！
学校oj题目标号
1.16330糖果
2.15731排队布局
说实话，整体而言挺简单的，主要要注意的就是约束条件的分析