11.8训练日记

这周我学习了最小生成树、负环、差分约束、最近公共祖先 以及 有向/无向图的双连通分量问题。

最小生成树：
最小生成树问题一般都不是很难，我目前做到过的比较有难度且只考察最小生成树的题目就只有次小生成树问题（后面我会写题解的）了，不过最小生成树问题可能会与一些别的算法来进行结合考察。有关最小生成树的两个基本算法：prim算法和kruskal算法在上周都说过了，这里就不重复说了。

负环：
负环问题是用spfa算法求解的。负环一般也没有什么难题，大多数负环问题都是和其它算法进行结合考察的。我见过的有01分数规划问题+负环 和 差分约束问题+负环的问题。
注：对于spfa求负环，有两种优化方式：
1.将spfa中的队列改为栈。
2.记录循环次数：如果循环了3*n次还没有结束，一般就是存在负环了，可以直接退出（这种方式比较的玄学）。
这两种方法都可以提高spfa求负环的速度。
相关题目：
01分数规划：观光奶牛、单词环
差分约束：糖果、排队布局

这里要说明一个问题：我上周写总结时觉得一个题的建图一般不会太难，但是我发现是我错了：建图其实是可以搞得非常难的。比如差分约束的问题
差分约束：
差分约束问题的难点就在于如何把题目中的要求抽象成一个图（建图）。差分约束问题一般是要先把题目中的条件化为一组组的不等式，然后将这些不等式抽象成图中的边，再来建图。并且一般差分约束问题还会有很多的隐含条件，这个就需要我们自己根据题目来想了。
对于差分约束问题，一旦图建出来了，这个题目基本上就做出来了。除了建图，还有一个问题需要我们注意：如果是求最大值，我们需要求最短路；如果是求最小值，我们需要求最长路。
相关题目：糖果、排队布局、区间、雇佣收银员

最近公共祖先（lca）：
即求在树上的两个节点最近的公共祖先节点问题。这个算法一般也不太会单独出现，主要是和其它算法进行结合考察。
最近公共祖先问题有两个比较常用的算法：
倍增法（在线算法 O(nlogn+qlogn)）：

1. 需要的预处理出的数组：
   fa[i][j] //表示从i节点开始，向上走2^j步所能到达的节点。
depth[i] //表示i节点的深度
2. 求两点lca的步骤：
   1）先让两个节点跳到同一层。
   2）让两个节点同时往上跳，跳到它们最近公共祖先的下一层为止。此时的答案即为：fa[a或b][0]。

tarjan算法（离线算法 O(n+q)）
tarjan算法的流程不太好描述（也可能是我还没完全理解），这里就先不进一步的写它的原理了。
相关题目：次小生成树（通过lca对于求次小生成树算法进行优化）、闇の連鎖（lca+树上的差分）。

双连通分量问题：
对于双连通分量问题，我觉得最常见的应用就是用来缩点了，在缩点之后，再利用缩点带来的自然的拓扑序进行求解问题的答案。因此，双连通分量问题一般也是结合其它算法来进行考察的。
有向图和无向图的双连通分量求解都是用的tarjan算法，其原理和代码也基本相同。
相关题目：
有向图的双连通分量：学校网络、 最大半连通子图、银河
无向图的双连通分量：冗余路径、矿场搭建

以上就是我这周训练的总结了，下周的话就是给图论收个尾，即把剩下的二分图、欧拉回路、拓扑排序三部分的习题做完。然后就是把前面缺的一大堆题解全部补上，就作为是复习了。之后的下下周就准备搞数论的内容了。