图论

DFS

记录一下一个OI中没怎么学会的知识点

上图是一个DFS遍历，pre数组记录了每个节点最初被访问的时间，post数组记录了每个节点最后被访问的时间(进出栈的时间)

根据两个数组，可以将所有边分为四类

树边(Tree Edge): DFS 树中的边
后向边(Back Edge): 从一个节点到其祖先的边
前向边(Forward Edge): 从一个节点到其子孙(非直接)的边
横叉边(Cross Edge): 除了上述三种边之外的边(在 DFS 树中要先往上再往下)
- 注意横叉边肯定是从右往左的，否则如下图，虚线边会先被访问，就不是横叉边而是树边了
- 这也意味着无向图不会有横叉边

它们的性质如下

Kosaraju 算法

给定一个图 $G = (V, E)$，考虑如何求出它的强连通分量(SCC)

如上图，如果我们将其看成一个由 SCC 构成的 DAG，在叶节点进行一次 DFS 找到所有能访问到的节点，就是一个 SCC(因为叶节点只进不出)，然后删去这个叶节点，依次类推。

所以我们只需要设计一个算法，使得他能够“倒序”访问这些节点即可

我们考虑使用之前定义的 post 数组，如果在 $G$ 中有从强连通分量 $C$ 到 $C'$ 的边，那么 $C$ 中的最大 post 数一定大于 $C'$ 中的最大 post 数，所以最大的 post 数对应的节点一定是源(source)

我们定义图的转置 $G^T = (V, E^T)$, 其中 $E^T = \{(u, v) | (v, u) \in E\}$，通俗的说就是将所有边的方向反过来，那么在 $G^T$ 中，最大的 post 数对应的节点一定是 $G$ 中的汇(sink)，从大到小依次是原图中汇到源的拓扑序

在 $ G^T $ 上运行 DFS, 得到每个节点的 post
在 $ G $ 上运行 DFS, 按照 post 从大到小的顺序访问节点，每次访问到的节点都是一个 SCC

HW4Q4 半联通

对于一个有向无环图，定义半联通性(semiconnectivity)为：对于任意两个节点 $u, v$，存在一条从 $u$ 到 $v$ 的路径或者从 $v$ 到 $u$ 的路径。求证：对于一个有向无环图，它是半联通的充要条件是存在一条可以访问到所有节点的路径

充分性显然，下证必要性
对于这个有向无环图，可以进行拓扑排序，得到一个拓扑序列 $v_1, v_2, \cdots, v_n$，因为有向无环，所以没有后向边，考虑拓扑序列中的任意点对 $v_i, v_{i+1}$，只能存在 $v_i \rightarrow v_{i+1}$ 的边，否则 $v_{i+1}$ 就会有 $v_i$ 的后向边，所以 $v_i$ 到 $v_{i+1}$ 有一条路径，那么我们就找到了一条从 $v_1$ 到 $v_n$ 的路径

HW4Q5 2-SAT问题

一个2-SAT问题是指，给定一个布尔表达式，其中每个子句都是两个文字的析取，求是否存在一种赋值方式使得表达式为真。例如，$(x_1 \vee x_2) \wedge (\neg x_1 \vee x_3) \wedge (\neg x_2 \vee \neg x_3)$。

建图

把合取转化为蕴含，然后把蕴含转化为边，最后把每个文字转化为两个点，分别表示自身和否定(如 $x_1$ 和 $\neg x_1$)，然后把蕴含转化为边，如 $(x_1 \vee x_2)$ 转化为 $(\neg x_1 \rightarrow x_2) \wedge (\neg x_2 \rightarrow x_1)$，然后把蕴含转化为边

获得答案

2-SAT 问题有解等价于图中不存在 $x$ 和 $\neg x$ 在同一个强连通分量中，因为如果存在这样的强连通分量，那么就有 $x \rightarrow \neg x$ 和 $\neg x \rightarrow x$，所以 $x$ 和 $\neg x$ 不能同时为真，所以没有解
反之如果不存在这样的强连通分量，那么就可以按拓扑序列从后往前赋值即可(注意，赋值一个文字的否定为真意味着将其赋值为假)，对一个 SCC 赋值完之后考虑它的父 SCC

HW6Q3 最小 $\infty$-范数割集

给定一个无向连通图，求一个割集，使得割集中的边的 $\infty$-范数最小，即 $\max_{e \in E'} w(e)$ 最小，其中 $E'$ 是割集中的边，$w(e)$ 是边 $e$ 的权重。要求复杂度为 $O(|E| \log |V|)$

翻译一下就是最大边权最小。一个简单的方法是对边权二分。但是在这里详细分析一下另外一种利用 MST 的 Cut Property 的方法，就是先求出一个 MST，然后对于 MST 中最小的那条边，输出这条边对应的 MST 中的割集即可。

正确性证明

先复习一下 Cut Property: 对于一个无向连通图 $G = (V, E)$，对于任意一个割集 $E'$，如果 $e$ 是 $E'$ 中的最小边，那么 $e$ 一定属于 $G$ 的某个最小生成树

此外我们需要一个性质: 一个图的两棵最小生成树，边的权值序列排序后结果相同

证明: 设最小生成树有n条边，任意两棵最小生成树分别称为A, B，其中A 的边权递增排序为 $a_1, a_2, \cdots, a_n$，B 的边权递增排序为 $b_1, b_2, \cdots, b_n$
假设在第 $i$ 个位置 $a_i \neq b_i$，不妨设 $w(a_i) \geq w(b_i)$
- 如果 A 中包含 $b_i$，则必存在 $j$ 使得 $w(a_j) = w(b_i)$，那么 $w(a_i) \geq w(b_i) = w(a_j) \geq w(a_i)$，它们边权都相等，调换一下顺序也不影响
- 如果 A 中不包含 $b_i$，那么把 $b_i$ 加入 A 中，必然会形成一个环，环中的边权都不大于 $w(b_i)$。另一方面，B 不可能覆盖整个环，必有某条边是仅仅属于 A 而不属于 B 的(这意味着不是前面的公共部分)，设为 $a_j$，那么 $w(a_j) \leq w(a_i) \leq w(b_i) = w(a_j)$，它们边权都相等，调换一下顺序也不影响

有了这两个性质，原算法的正确性几乎是显然的

贪心算法

Horn-SAT

定义: 一个 Horn-SAT 公式是一个由 Horn 子句构成的公式, 其中 Horn 子句是至多有一个正文字(positive literal)的合取范式

一共只有两种: $\neg x_1 \vee \neg x_2 \vee \cdots \vee \neg x_i$ 和 $\neg x_1 \vee \neg x_2 \vee \cdots \vee \neg x_j \vee x_{j+1}$
其中后者可以写成蕴含形式: $ (x_1 \wedge x_2 \wedge \cdots \wedge x_j) \rightarrow x_{j+1}$

算法很简单，一开始所有变量都为假，然后每次都看哪个蕴含式的前提都为真，就把它的结论设为真。一开始只有单个变量的"蕴含式"(没有前提)会被考虑，后面就是看哪些前提一定满足，就把结论设为真

近似算法

近似算法中一个重要的定义是近似比(approximation ratio): 一个算法的解与最优解的比值

一般贪心算法都是比较优秀的近似算法, 如

集合覆盖问题

一个最直观的想法就是每次选能覆盖最多的集合，这显然不是最优(如上图)，但是可以证明它的近似比为 $ln n$

事实上如果最优解的集合数为 $k$, 那么根据平均数原理, 至少有一个集合覆盖了 $\dfrac{n}{k}$ 个元素, 每次选覆盖最多的集合可以使得原集合的大小缩减到之前的 $\dfrac{k-1}{k}$, 经过 $k \ln n$ 次迭代后, 剩下的集合数为 $1$

HW6Q4 Firefighters

有一颗 $N$ 个节点的树，可以建造 $K$ 个消防站，定义，某个消防站的响应时间为其到树上任意一个节点的最大距离，所有消防站的响应时间是他们个别的响应时间的最大值。考虑一个贪心算法，每次在距离当前消防站最远的节点建造消防站，证明这个算法的近似比为 $2$

证明

设最优解的响应时间为 $R_{opt}$，贪心算法的响应时间为 $R_{greedy}$，那么我们可以得出一个重要性质就是对贪心算法给出的 $K$ 个消防站，他们之间的距离都会不小于 $R_{greedy}$，因为每次都是在距离当前消防站最远的节点建造。在全部建完之后最远距离为 $R_{greedy}$，在此之前都不会小于它

如果任何两个消防站之间的距离小于 $2R_{opt}$，那说明现在已经可以了
如果 $R_{greedy} > 2R_{opt}$，那么任选两个贪心解法中的消防站 $a,b$ 和一个最优解中的消防站 $s_{opt}$ 有 $ dis[a][b] \leq dis[a][s_{opt}] + dis[s_{opt}][b] \leq 2R_{opt} < R_{greedy}$，矛盾

动态规划

HW8Q2 高楼丢鸡蛋

经典 Google 面试题，给定 $n$ 层楼和 $m$ 个鸡蛋，定义 $f(n, m)$ 为最坏情况下确定鸡蛋摔不碎的最少尝试次数，求 $f(n, m)$

在 HW7 中将状态直接设置为 $f(n,m)$，但是可以考虑间接地做这个题，将状态设置为 $M(x,m)$ 表示 $m$ 个鸡蛋在 $x$ 次尝试下能确定的最高楼层数，则转移方程为

\[M(x, m) = M(x-1, m-1) + M(x-1, m) + 1 \]

这样考虑: 对于 $ M(x, m)$，在 $M(x-1, m-1)+1$ 层丢一次鸡蛋，如果碎了，那么剩下的 $m-1$ 个鸡蛋可以确定 $M(x-1, m-1)$ 层，如果没碎，那么剩下的 $m$ 个鸡蛋可以确定 $M(x-1, m)$ 层，还要加上这一次(因为如果上面的层测出来是 0，那就对应测试的这一层)