差分约束小结
感觉这玩意挺简单的。出不了太难的题啊。
这种奇怪的图是可以跑最长路的，因为负环迟早要退出。
1.SPFA负环
一般来说要先判图中是否存在正/负环，可以用SPFA记录每个点松弛次数判断。
每个点在一开始都扔进队列，或者新建超源与点连边均可。
第二种更加有逻辑，且能处理点有初始值的情况，方式为将超源到点的边权赋为点权，点到超源的边权赋为点权相反数（有些题目是乘要赋值为倒数）。
2.floyd求上下界
更加准确地求出两点间点权差上下界，便于统计方案数等。
但是注意只有强连通分量内部才能得到真正的点权差范围。于是需要先缩点，强联通分量内部用floyd求点权差范围，强连通分量之间并不影响，只要满足边条件就可以把差无限拉大。
最短路求出的是满足所有条件的最大值，最长路求出的是满足所有条件的最小值。这是由最短/长更新方式决定的。可以发现最短路满足最小的限制，同时它恰好满足最小限制，即上界。最长路同理。