差分约束，虽然是带有“差分”二字，但是实际上通常是归属于图论这一类问题。

差分约束主要的表现形式是求满足一组数值上大小关系条件的最大/最小值。

大小关系条件就是“大于，小于，等于”这种。

通常在拿到一组条件之后，需要确定求的是最大值还是最小值，这会关系到是求最短路还是最长路。

如果是求最大值，一般就是求最短路。与之相对的如果是求最小值就是求最长路。

我们是如何将一组数值上的大小关系条件转换为图论问题的？

我们会将一个关系变为一条边，而在边的两端就是满足这个关系的两个客体。而且通常需要根据是求最大值还是最小值并根据贪心的思想，先将这个关系统一转换为小于等于或者大于等于。

举个例子，对于求最大值来说，需要将所有的关系转换为小于等于，最终的答案就是求满足这一组小于等于关系的一个交集。通过跑最短路，可以不断的去求这个交集。

比如现在有两个值a，b，并且有三个关系

a ≤ b + 1

a ≤ b + 2

a ≤ b + 3

a ≥ 0

b ≥ 0

需要求的是满足这个条件每个数的最大值，假如给a，b分别设置为1，2号点，那么对于前三个关系可以看做是b分别向a连了3条边，权值分别是1，2，3。而对于最后两个条件可以看做是a，b两个点分别向超级源点0连了一条边权为0的边。之后去跑最短路，可以求出a，b两点向超级源点的最短的距离是1，0。所以满足这个条件的最大值就是1，0

上午早十是数据库，课上把上一周没有看完的差分约束 + tarjan + topo 的一道题目看完。其实最近感觉要是想要安安静静的学习一段时间也是某种奢求，对于我这种“课外活动”比较多，有的时候都会认为自己在学校不是以一个学生的身份而是以一个社会人的身份在各种组织里面来回游走。所以当真正开始有一些空余时间之后还是会变得有些不知所措，有点忘记学生应该如何学习。实际上能够两耳不闻窗外事，一心只读圣贤书是一件很幸福的事情。

最近看书看到这个up，b站上就去关注了一下。

https://space.bilibili.com/1317344920?spm_id_from=333.1387.follow.user_card.click

有一说一他的生活比较接近我理想的状态。也恰好是在现代社会。

我比较喜欢的生活就是这样一边做远程，然后一边到处玩，然后保持单身。挺好的。

唉唉，最近好焦虑。

上面应该有附图的，但是图床貌似出了点问题，得找个时间修一修。