图论
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，那就对应测试的这一层)
线性规划
线性规划是一种优化问题，标准形式如下
maximize \(c^T x\)
subject to \(Ax \leq b\), \(x \geq 0\)
其中 \(A\) 是 \(m \times n\) 的矩阵，\(b\) 是 \(m\) 维向量，\(c\) 是 \(n\) 维向量，\(x\) 是 \(n\) 维向量
对于以下非标准形式，容易将其转化为标准形式:
- 求最小值: 将目标函数取负
- 约束条件为 \(Ax \geq b\): 转化为 \(-Ax \leq -b\)
- 约束条件为 \(Ax = b\): 转化为 \(Ax \leq b\) 和 \(-Ax \leq -b\) (一个大于等于一个小于等于)
- 约束条件为 $ x \leq 0$: 令 \(x = -z\)，转化为 \(z \geq 0\)
- 对 \(x\) 没有约束: 令 \(x = x^+ - x^-\)，转化为 \(x^+, x^- \geq 0\)
对偶形式
canonical LP 的 dual 如下
minimize \(y^T b\)
subject to \(y^T A \geq c^T\), \(y \geq 0\)
弱对偶: 对于任意可行解 \(x\) 和 \(y\)，有 \(c^T x \leq y^T b\)
强对偶: 最优解 \(x^*\) 和 \(y^*\) 满足 \(c^T x^* = y^{*T} b\)