05 Greedy

最小生成树

在无向图中选出$|V|-1$条边，使得生成树的边权和最小，这就是最小生成树问题。

Kruscal算法

我们有一个看上去有些草率的做法：给所有边按照权值从小到大排序，假设所有边都消失了，那么以从小到大的顺序加边（如果这条边对应的两点间已经有路径就跳过不加），等到加完第$|V|-1$条边时，我们会得到一棵“生成树”。由于每一次我们都在选择当前最优的策略，我们并没有自信我们得到的生成树就是“最小生成树”。但我们可以证明，这就是最小生成树。这就是最小生成树的Kruscal算法。这样的算法称为“贪心”算法，每一步我们保证在当前状态下最优，最后恰好能证明这就是最终的最有答案。

我们归纳地证明：当我们以从小到大的顺序加入两端点原本并不连通的一条边$(u,v)$时，一定存在以先前已经选择的边和这条边为基础构成的某棵最小生成树。我们取一个包含$u$的点的集合$S$，以及它的补集$T$，要求这两个集合之间没有任何横跨的边是已经被选取了的（这是容易做到的，不妨把$S$设成$u$出发的连通块，$T$是其余的点）。假设不存在这样的最小生成树，那么随意取出某棵最终的最小生成树，点$u$和点$v$虽然不是树边，但通过生成树一定有一条路径相通，这条路径和边$(u,v)$恰好形成了一个环。并且，这条路径一定经过了另一条横跨边，记为$(p,q)$。由于我们是从小到达取边的，而此时$(p,q)$一定还没有被取，因此其权值必须比$(u,v)$大或与$(u,v)$相同。这时我们发现，如果我们断开$(p,q)$这条边，连接$(u,v)$这条边，我们依然能形成一棵生成树——断开$(p,q)$时，生成树变成了两个连通块，由于$p,u$同属一个连通块，$q,v$同属一个连通块，所以$(u,v)$会再次连通这两个连通块。$n-1$条边的$n$个点的连通块一定形成树（归纳证明）。如果$(p,q)>(u,v)$，那么我们得到了一棵更小的生成树，矛盾；如果$(p,q)=(u,v)$，那么我们得到了一棵包含$(u,v)$的最小生成树，矛盾。于是我们证明了Kruscal算法是正确的。

并查集

为了实现Kruscal算法，我们需要有一个算法能够高效地维护“集合”。我们需要一个数据结构，能够判断两个点是否属于同一集合，并支持集合之间的合并。

并查集是有向森林，森林里的每一棵树就是一个集合。除了根节点以外，每个节点有一个父节点。于是，判断两个节点是否属于同一集合只需要判断两个节点是否在同一棵树里，而这只需要不停网上查询父节点，判断所在根节点是否相同；合并两个集合就是合并两棵树，我们只需要将其中一棵树的根节点指向另一棵树的根节点，前者不再是根节点而有了一个新的父节点。

上面的合并过程有可能会使得“树”退化为“链”，这样每一次查询就可能需要$O(|V|)$的时间。在Kruscal中， 我们会进行$O(|V|)$次合并，最多可能进行$O(|E|)$次查询，因此这样的复杂度是不够优的。我们有两种方法来优化合并：

按秩合并（Union by Rank）

第一种方法称为“按秩合并（Union by Rank）”。我们对每个节点维护一个rank，rank表示以这个节点为根的子树的深度。我们注意到，并查集在初始时，每个节点都是根节点，因此“子树”的出现一定是因为曾经有集合合并到了这个节点上（当时这个点还是根节点）。这里，我们又要大量用到归纳法。初始时设每个点的rank都为0，因此我们可以归纳地假设当我们进行一次合并的时候，每个点都有当前的rank。我们按照rank来合并：我们比较被合并的两个集合的rank的大小，并规定必须是rank小的树的根的父节点指向rank大的树的根节点（相等则都可以）。如果这两个rank的大小关系是严格的，则大的那棵树深度至少比小的大1，因此合并之后，大树的深度不变，所有对于所有节点没有人的rank需要改变。而如果相等了，所有节点中只有大树的根节点需要做出改变，它要比原来增加1。通过这样的方法，我们就在全过程中维护好了rank的值。现在我们要证明，这样的合并方法能保证树的深度是$O(\log |V|)$的，因此Kruscal的算法复杂度可以做到$O(|E|\log |V|)$。（排序复杂度是$O(|E|\log |E|)=O(|E|\log |V|)$）

我们可以证明，rank为$k$的子树至少有$2^k$个节点——依然是归纳法！初始时每个点的rank都为0，每个子树都至少有$1$个节点。当我们要合并rank为$a,b$的两棵子树的时候，归纳地假设他们都已经分别有$2^a,2^b$个节点。如果$a>b$，那么合并后rank依然为$a$，这个子树将会拥有$2^a+2^b>2^a$个节点，满足；如果$a=b$，那么合并后rank为$a+1$，这个子树将有$2^a+2^b=2^{a+1}$个节点，依然满足。既然如此，那么就不可能有节点的rank会超过$O(\log n)$，因为这样的话它的子树必须有超过$n$个节点！所以树的深度是$O(\log n)$，查询的复杂度就是$O(\log n)$了。合并两个节点的时候我们需要查询，而合并操作本身是$O(1)$的。

路径压缩

从某种意义上看按秩合并的复杂度已经达到了排序复杂度的瓶颈了。但是如果给定的边已经是有序的，或者说边权较小使得我们可以用桶排序等方法线性完成排序，那么复杂度的瓶颈反而变成了并查集了。我们想进一步把并查集的复杂度优化为线性。

我们在原来按秩合并的基础上加上一个操作，把查询中遇到的每个节点的父节点都更新为根节点（在代码中把return find(fa[x]);替换为return fa[x]=find(fa[x]);）。从直觉上我们会发现，每个点如果被查询到了就会紧贴在根节点下面，树的高度就不会太高。现在我们要严格地说明这一点。

如果仔细分析合并的过程，我们会发现，一个节点一旦被合并到了别的树上称为了子节点，它就永远没有机会修改它的rank了。换言之，rank的修改只会在当前的根节点上发生。路径压缩不会影响每一时刻的rank，也就是说，无论做不做路径压缩，所有时刻每个节点的rank都会和没有路径压缩时保持完全相同！——这可以归纳地证明，刚开始所有的rank是相同的，因为所有节点都是根节点。假设某一时刻所以rank都相同，那么我们会做出同样的选择将某一子树合并到另一子树，我们对rank的更新的判断完全是基于上一时刻的rank的，因此新一时刻的rank依然将保持相同。

既然如此，那么在路径压缩下，所有关于rank的性质都和之前相同。但注意，此时的rank不能再代表子树的深度，它只是一个抽象的符号了，或者可以看到子树的深度一定小于等于rank，因为路径被压缩了。

下面，我们对路径压缩的复杂度给出一个神奇的证明。如果分析单次查询的复杂度，我们难以给出一个小于$O(\log n)$的bound，因此我们必须转而分析总的复杂度，即分析“均摊复杂度”。每一次find消耗的时间可以等价地理解为“进行了多少次跳父节点的操作”，由于一条从小往上的链的节点rank值一定是单调递增的（这同样是由于，路径压缩并不会破坏父节点rank大于子节点这条性质），查询的复杂度就相当于这个rank序列的长度。我们把自然数分成这样的集合：

$\{1\},\{2\},\{3,4\},\{5,6,\cdots,16\},\{17,\cdots,2^{16}\},\{2^{16}+1,2^{2^{16}}\},\cdots$

由于$2^{65536}$已经足够大了，我们认为这6个集合就已经覆盖了所有的自然数。

我们来考虑每一次“跳跃”，这里的“跳跃”是指我们在每一次find操作中“从某一点走到它父亲节点”这一事实。我们只考虑“父节点不是根节点”的跳跃，因为父节点是根节点的跳跃只发生了find次数次，在Kruscal中是$O(|E|)$的，因此我们可以不管这一部分。而重要的是父节点不是根节点的跳跃，它们的rank都已经被定死了，与最终的rank相同。那么我们可以根据最终的rank把这些跳跃分成两类：一类是上述集合里rank跨集合的跳跃，一种是集合内部的跳跃。我们分别来计算这两种跳跃总共会发生多少次。

第一类比较简单：对于每一次find，这种跳跃最多发生5次（6-1），那么我们总过做$O(|E|)$次find，第一类跳跃的总数也就是$O(|E|)$。

第二类比较复杂，我们不对每一次find来计数，而是对每个节点来计数。（我们只考虑某一个特定集合内部的跳跃，之后把结果乘以6即可。）我们注意到一个非常重要的事实：每经过一次跳跃的节点就会被路径压缩，它将会有一个新的父节点，这个父节点的rank一定比原来的大。所以，这个集合“内部”的跳跃发生在同一个节点上的次数是有限的。比如我们计算在第四个集合内部发生的跳跃，这首先要求节点的rank落在这个范围内。对于rank为$k$的节点，取它所在集合的右边界$2^m$（比如rank为20就取$2^{16}$），那么这样的一个节点在这个集合内部最多发生$2^m-m \leq 2^m$次内部跳跃，这之后的跳跃会让这个节点离开当前集合，数它就不再是我们目前的工作了。由于rank为$k$的节点的子树大小至少为$2^k$，那么在所有的节点中，rank为$k$的节点不能超过$n/2^k$个，不然总的节点个数就会超过$n/2^k \cdot 2^k=n$个。那么一个当前集合里的节点总数最多有多少呢？我们可以直接放缩，统计所有rank大于$x$的节点个数，然后令$x$取$0,1,2,4,16,65536$即可：根据我们的结论，rank大于$x$的节点总数小于等于$\dfrac{n}{2^{x+1}}+\dfrac{n}{2^{x+2}}+\cdots\leq\dfrac{n}{2^{x+1}}\cdot \dfrac{1}{1-\frac{1}{2}}=\dfrac{n}{2^{x}}$。而我们要数的每个节点在这个集合里的节点内部跳跃总数不超过$2^x$，因此所有发生在这个集合里的内部跳跃次数不超过$n$。这样我们就数完了所有发生在这个集合里的跳跃。总共有6个这样的集合，所以所有发生在内部的跳跃不超过$6n$。因此第二种跳跃的总次数为$O(|V|)$。

所以综合起来我们证明了，在路径压缩下的按秩合并维护的Kruscal算法除去排序以外的复杂度为$O(|E|)$。

现在我们理解了为什么要用这么“奇怪”的方式来划分集合：我们关键是注意到了$rank$大于$x$的节点总个数不超过$\dfrac{n}{2^x}$个，因此我们期待，如果能够在rank大于$x$的集合中的点的内部跳跃次数都不超过$2^x$，那么就能把集合内部的跳跃次数用$n$来bound。而我们看到我们是用区间长度来bound跳跃次数的，所以这就自然地要求我们令$x$开头的区间长度不超过$2^x$。同时还要满足，总的集合个数是“常数”个，这样才能避开分析跨集合的跳跃——于是我们发现，这种“奇怪”的划分方式恰好是满足我们的需要的。

Set Cover

在图上定义选一个点就代表覆盖了与这个点相邻的所有点，问最小选几个点就能覆盖所有的点，这就是Set Cover。

这是一个NP-hard问题，因此目前没有多项式算法。我们现在来考虑一个贪心算法的近似性：我们维护图上有哪些点还没被覆盖，每次选择能覆盖最多未覆盖节点的点。我们来证明，如果最小点覆盖的答案是$k$，我们的算法能给出一个不超过$k\ln n$的答案。

我们设第$t$次选点以后还有$n_t$个节点没被覆盖。在任何时候（无论我们已经覆盖了哪些边），我们都可以通过上帝视角选择最优的那$k$个点覆盖所有点，因此这$k$个点也就一定能覆盖剩下的$n_t$个点。这说明这$k$个点中至少有一个节点“新覆盖”了$n_t/k$个点，因为如果所有节点新覆盖的节点数都小于$n_t/k$，这些点就不能把剩下的点盖完，矛盾。因此$n_{t+1} \leq n_t - n_t /k$。这样我们就得到了递推关系

$\dfrac{n_{t+1}}{n_t} \leq 1-\dfrac{1}{k}$

累乘，得到$\dfrac{n_t}{n_0} \leq (1-\dfrac{1}{k})^{t} \leq e^{-\frac{t}{k}}$。当$t=k\ln n$时，$n_t \leq 1$。这就说明点已经选完了。