qbxt day2

DFS 生成树

对于任意一棵 DFS 生成树，其必定只有返祖边，没有横叉边，在求割点和强联通分量上方便很多。

最小生成树

求法：https://www.cnblogs.com/yifan0305/p/17363255.html
严格次小生成树、非严格次小生成树。

最短路问题

• Floyd
  求最短路、最小环，传递闭包。
  链接：在写着，会补得。
• dijkstra
  堆优化。
• spfa
  他死了
  有负边权的时候用。
• 次短路问题

差分约束

差分约束问题是指，现有 \(n\) 个变量 \(x_1 ,x_2 ,\cdots ,x_n\) ，并有 \(m\) 个约束条件，即 \(x_i − x_j \le c_k\) ，需要求出满足所有条件的一组解。
考虑将每个变量视为一个结点，每个约束视为一条边，这样约束条件就等价于最短路限制，每个结点的 dis 也就是变量的取值。
若能够找出每个结点的最短路，则对应原差分约束的一组解，若存在负权环，
则差分约束问题无解。

剩下的就是题目了。