差分约束
建边套路
优化套路
如果数据明显 $SPFA$ 复杂度不正确，可以考虑把 $queue$ 换成 $deque$ 和 $stack$。
建立超级源点的时候直接把所有点入队，然后把超源架空即可。
最长路与最短路问题
最短路建图的时候只需要建立上界约束，而最长路建图需要建立下界约束。
以下内容摘自 do-while-true 的“原来我不会差分约束”：
差分约束系统提供了通过图论建图以最长路/最短路的形式刻画变量之间的不等关系。常见的应用是判断不等关系是否有合法解。
对于最短路，我们将 $x_v−x_u≤w$ 描述为 $dis_v≤dis_u+w$，感性理解一下，在这里描述的是 $x_v$ 的上界，而且通过跑最短路找到了 $x_v$ 的上界。虽然跑的是”最短路”，但在不等式组的意义下 $x_v$ 可能会更小，所以这里是在满足不等式组的条件下让 $x_v$ 取到了它的上界。
类似地，如果想要用最长路来跑差分约束，得到的是每个变量的下界。
总结：最短路跑出来的是每个变量最大可能的值，最长路跑出来的是每个变量最小可能的值。
缩点题目套路
以重新建图后的图考虑。
从一个点可以到达联通块内任意点的点性质：入度为 $0$。
加边变为大联通块：$\max\{入度为0的点数量,出度为0的点数量\}$。
题目带 $dfs$：记得判断是否经过该点，不要有环就不打 $tag$。
边双分量题目套路
- 对于一个有桥图加边变成双联通图，至少要加的边数至少为边双子图收缩后的 $DAG$ 上度为 $1$ 的节点数 $\frac{L+1}{2}$。