「赛前备战」NOIp2020-提高图论训练

博主太菜，可能会炸联赛，于是恶补一下 QAQ

题目比较基础，动态更新

Summarize

简单概述了一些基础图论算法。

复杂度中 (V) 或 (n) 为顶点数，(E) 或 (m) 为边数。

最小生成树（MST）

Prim 算法：适合稠密图，并且稠密图不需堆优化。复杂度：朴素 (O(V^2))，堆优化 (O((V+E)log V))。

Kruskal 算法：适合稀疏图，最为常用、最简单的 MST 算法。复杂度 (O(Elog E))。

Borůvka（Sollin）算法：最古老、最鲜见的算法。复杂度 (O(Elog V))。

单源最短路径（SSSP）

Dijkstra 算法：在任何数据下都很稳，但是跑不了负权边。复杂度：朴素 (O(V^2))，堆优化 (O((V+E)log V))。使用 STL 二叉堆为 (O((V+E)log E))。

Bellman-Ford 算法：效率不高，但可以跑负权边、判负环。时间复杂度 (O(VE))。经过队列优化后可以在随机数据下跑得飞快，但仍然可以被卡回 (O(VE))。队列优化后的 Belllman-Ford 算法常被称为 SPFA 算法。

多源最短路径（APSP）

Floyd 算法：基于动态规划，最简单的最短路算法，复杂度 (O(V^3))。拓展：最小环问题。

Johnson 算法：Bellman-Ford 处理负权，然后 (V) 遍 Dijkstra。时间复杂度 (O(VElog V))。

差分约束

将不等式约束关系转化为图，最后用 Bellman-Ford 算法跑最长路。

树的直径

树上最长的路径为树的直径。下面两种算法都是线性的。

两遍 Dfs（Bfs）：可以求出具体的直径。

动态规划：可以处理负权。

树的重心

考虑一个点，以它为根的树中，最大的子树节点数最少，我们把这个点称为树的重心，

一般用动态规划求。

最近公共祖先（LCA）条

倍增法：预处理时空复杂度 (O(nlog n))，询问 (O(log n))。

轻重链剖分：预处理时空复杂度 (O(n))，询问 (O(log n))。

RMQ：预处理时空复杂度 (O(nlog n))，询问 (O(1))。

Tarjan（离线）：时空复杂度线性。

树链剖分

包括轻重链剖分、长短链剖分、虚实链剖分。最常用的是轻重链剖分。

轻重链剖分后产生的重链数不超过 (O(log n)) 条。

拓扑序

每次取出其中一个无入度的点，最后形成拓扑序。

若图没有拓扑序则不是 DAG。

强连通分量（SCC）

有向图中一个顶点两两互相可达的一个极大子图被称作强连通分量。

Tarjan 算法：最常用，复杂度 (O(n+m))。

Kosaraju 算法：比较少见，复杂度 (O(n+m))。

非 DAG 图经过 SCC 缩点后是一个 DAG。

割点

无向图中，移除该点使联通分量个数增加，那么这个点为割点。

用 Tarjan 算法可以在线性时间内求出图中所有割点。

桥

无向图中，移除该边使联通分量个数增加，那么这条边为桥（割边）。

用 Tarjan 算法可以在线性时间内求出图中所有的桥。

点双连通分量（v-BCC/v-DCC）

无向图中，一个顶点两两间有至少两条点不相交的路径的一个极大子图被称作点双连通分量。

v-BCC 中不存在割点。

边双连通分量（e-BCC/e-DCC）

无向图中，一个顶点两两间有至少两条边不相交的路径的一个极大子图被称作点双连通分量。

e-BCC 中不存在桥。

2-SAT

2-SAT 是一种特殊的逻辑判定问题。参考：https://www.luogu.com.cn/blog/user9012/post-2-sat-lve-xie

借助 Tarjan 算法求 SCC 可以求解 2-SAT 问题。

二分图判定

直接黑白染色。

二分图匹配

最简单的是匈牙利算法，复杂度 (O(n^2 m))。

数据结构优化建图

常用的有（高维）线段树、KDT 等。

Content

「Codeforces 888G」Xor-MST 生成树
「AtCoder JSC2019 Qual E」Card Collector 生成树
「HDU 4725」The Shortest Path in Nya Graph 最短路
「2018-2019 XIX Open Cup, Grand Prix of Korea」Dev, Please Add This! 2-SAT
「2015 ACM Amman Collegiate Programming Contest」Bridges 边双连通分量 树的直径与重心
「HDU 4370」0 or 1 最短路 最小环
「NOI2019」弹跳 最短路 数据结构优化建图
「Codeforces 1280C」Jeremy Bearimy
「AtCoder AGC018D」Tree and Hamilton Path 树的直径与重心
「APIO2010」巡逻 树的直径与重心
「UVA 1464」Traffic Real Time Query System 点双连通分量
「POJ 2942」Knights of the Round Table 点双连通分量 二分图判定
「Aizu 2991」XORANDORBAN 2-SAT
「TJOI2019」大中锋的游乐场 最短路

「Codeforces 888G」Xor-MST

update - 2020.8.4

此题需要用到一个叫 Borůvka 的最小生成树算法，大致就是对现在的每一个连通块都找一遍的最短边，最后每个连通块择优，将这些边全部连上。这样复杂度之正确的原因可以参考启发式合并，(O(|E|log |V|))。

对于此题，我们以可以用这样的思路来“择优合并”，即选取两个结点 (u, v)，使得 (a_u oplus a_v) 最小，然后合并。现在如何找到这个最小的就是个问题。

对于两个二进制数 (x = (10001010)_2,y = (10000110)_2)，前 (4) 位相同，即 ( ext{lcp} = 4)，那么异或一次前四位都是 (0)。我们优先考虑二进制下 ( ext{lcp}) 较大的。

和前缀有关，于是可以断定是 01-Trie。转化到树上，lcp 就成了两个叶子的 LCA，那么我们就该优先考虑 LCA 深度较深的。

遍历整颗 Trie，找到这些 LCA，然后对于一个 LCA，枚举左儿子值域中的所有数 (a_i)，然后在右子树中查询，并使路径上的 0/1 值尽量和 (a_i) 一样以达到异或后最小化的目的。最后这些查询的最小值的和即为所求。

时间复杂度 (O(nlog nlog a))。

「AtCoder JSC2019 Qual E」Card Collector

update - 2020.8.4

如果把每一行、列都视作一个点，把卡片视为边，我们会得到一个 (w+h) 个点， (n) 条边的图。若有一张第 (i) 行第 (j) 列的卡片，那么就视作一条结点 (i)，(h+j) 之间的边，权值为卡片数值。

考虑题面上取卡片的过程如何转换到图上：我们假定图有向，那么在第 (i) 行取走第 (j) 列的卡片，就相当于一条 (i o j+h) 的边；同理，在第 (i) 列取走第 (j) 行的卡片，就相当于一条 (i + h o j) 的边。

试着研究最后取完建出的新图的性质。一个结点的出度最多为 (1)，那么整个新图就是（内向）基环树的森林。最后将边转为无向。

题目要求权值最大化，那么就是求图上的最大生成基环树森林。要求最大生成基环树森林，可以仿照 Kruskal 算法贪心地取边，与一般 MST 的不同之处就是需要判环，实现要点是一个点所在连通块中最多一个环。

时间复杂度 (O(nlog n))。

Code : https://strncmp.blog.luogu.org/solution-at5168

「HDU 4725」The Shortest Path in Nya Graph

update - 2020.8.4

繁琐的最短路题，重点在与怎么建图。

不能直接在层之间的点暴力连边，边数显然可以被卡到 (O(n^2))。

我们可以构造 (2n) 个虚拟结点，编号在 ([n+1, 2n]) 的结点为入点，入点 (n+l) 引出边连向 (l) 层的所有结点；编号在 ([2n+1, 3n]) 的结点为出点，出点 (2n+l) 接受 (l) 层所有点向此的连边。

然后对于所有的层 (lin[1, n))，有连边 $2n+l o n + l + 1 $，(2n+l+1 o n+l)。

最后一边 Dijkstra 跑出最短路，时间复杂度（STL 二叉堆） (O(T(n+m)log m))。

「2018-2019 XIX Open Cup, Grand Prix of Korea」Dev, Please Add This!

update - 2020.8.5

物体只能向一个方向运动到底，那么我们可以把极长的一个横块或竖块作为一个整体处理。（类似于一些二分图的题对网格图的处理手段）

预处理出这些块，我们将其视作顶点，显然顶点的规模为 (O(w imes h))。

然后根据题意，将题目中的条件转化为图上的信息：若一个块 (i) 的端点与另一个块 (j) 的中部相交，，单那么顶点 (i) 向 (j) 连一条单向边向边的原因显然是因为 (j) 不能直接到达 (i)；若一个块 (i) 的端点与另一个块 (j) 的端点相交，那么那么顶点 (i) 向 (j) 连一条双向边，可以互相到达。实现时可以用邻接矩阵。

首先我们可以根据原网格以及建好的图得出三个要素：

对于一个 ( exttt{*}) 的格子，一定有一个横块或竖块被经过，或者说“被选中”。形式化地讲，设横块、竖块的编号为 (x, y)，那么一旦不选 (x)，那必须选 (y)，反之亦然（( eg x o y, eg y o x)）。
起始点所在的两个块都不能（直接或间接）到达某个块 (i)，那么有 (x o eg x)，因为我们不能选这个块。
对于两个无法互相（直接或间接）到达的点 (x, y)，我们如果选了 (x) 就无法再选 (y)，反之亦然。形式化地讲，(x o eg y, y o eg x)。

然后将这些条件整合，使用 2-SAT，时间复杂度 (O(w^2 imes h^2))。

「2015 ACM Amman Collegiate Programming Contest」Bridges

update - 2020.8.5

首先在一个 e-BCC（边双联通分量）中加边不会减少桥的数量。那么我们可以先按 e-BCC 缩点，在新图（树）上加边，这样新树上的边都是原图的桥，那么加边就有作用。

那么如何最小化桥数呢？我们可以在树上构造出一个尽量大的环，那么这些环上的边都不再是桥了。

于是找到一段最长的链（直径），在链的两端连边即可达到消除桥的目的。

答案即为 e-BCC 的个数减去缩点所得的树的直径上的点数。

时间复杂度 (O(Tn))。

「HDU 4370」0 or 1

update - 2020.8.5

玄妙图论题。

首先题目给定一个矩阵 (C)，我们把它当作带点之间的边权：第 (i) 行第 (j) 列的元素 (C_{i, j}) 表示边 (i o j) 的边权为 (C_{i, j})。同样的可以把矩阵 (X) 作为需要构造的图边的选择情况。

尝试转化题中所给的限制：

(sum_{i=1}^n X_{1, i}=1) 表示结点 (1) 的出度为 (1)。
(sum_{i=1}^n X_{i, n}=1) 表示结点 (n) 的入度为 (1)。
(sum_{k=1}^n X_{k, i} = sum_{j=1}^n X_{i, j}) 表示对于结点 (2, 3, cdots , n-1)，出度等于入度。

最后所求 (sum_{1le i, jle n} C_{i,j} imes X_{i, j}) 即为所选边的边权和。

第一种显然的方案是，(1) 到 (n) 的一条最短路。

第二种是，两个分别经过结点 (1, n) 的长度 (ge 2) 的最小环。

接下来就简单了，有两种做法：

Floyd。注意这里的最小环和传统的有区别。初始设 ( ext{dist}(i, i) = infty)，然后正常跑 Floyd 即可。答案即为 (max( ext{dist}(1, n), ext{dist}(1, 1)+ ext{dist}(n, n)))。时间复杂度 (O(Tn^3))（(T) 为数据组数），比较卡。
Dijkstra（Spfa）。以 Dijkstra 为例，我们可以在开始时除了起点 (s) 外全部赋值 ( ext{dist}(i) = C_{s, i})，然后正常跑。最后跑三次即可，复杂度 (O(Tn^2))。Spfa 也可以用同样的方式处理。

「NOI2019」弹跳

update - 2020.8.5

神奇 K-D Tree（二维线段树）优化建图题。这里使用 K-D Tree。~~因为不会二维线段树~~

首先直接暴力连边会得到一个 (O(n^2)) 的优秀算法。考虑优化这个过程，由平面可以联想到 KDT。

建出 KDT 之后，我们用这颗树优化我们的建图过程。对于一个弹跳装置 ((p, t, L, R, D, U))，我们从结点 (p) 开始，向在规定区域内代表的 KDT 上的结点连一条 (t) 长度的边。最后将 KDT 上的边的边权视为 (0)，图就建完了。最后 Dijkstra 一波即可。时间复杂度 (O(nsqrt{n} log n))。

这么做看似完美，但由于 128 MB 的空间限制无法直接 AC，因为边数是 (O(msqrt{n})) 的（KDT 复杂度）。但实质上我们并不需要在建好 KDT 后就大力连边，KDT只是帮助我们知道一个点可以到达什么点。而且这个神奇时间复杂度也很难卡过。

我们称原图中的点为『实点』，KDT 上的点为『虚点』。为方便起见，设实点 (x) 对应的虚点为 (x+n)。

在跑 Dijkstra 时，我们有如下算法：

堆顶是实点：
- 对于其一弹跳装置 (y)，限定到达区域为 (A)，在 KDT 上进行搜索，设当前虚点为 (v)，那么按照 KDT 的套路：
  - 若子树 (v subseteq A)，直接松弛 (v)；
  - 若子树 (v cap A = varnothing)，跳出；
  - 若区域相交，先松弛实点 (v - n)，然后递归。
堆顶是虚点：
- 松弛其对应的实点；
- 松弛其在 KDT 上的左右儿子。

这样就达到绕开直接建图的目的。我们可以这样做的原因是，我们使用数据结构为工具，就已经能做到快速知道某个点可以到达的结点了，那么大力连边显然是冗余操作。

时间复杂度（STL 二叉堆） (O((n+m)log m + msqrt{n}))，空间只需要 (O(n+m))。

Code(~~写的很丑~~) : https://loj.ac/submission/892833

「Codeforces 1280C」Jeremy Bearimy

update 2020.8.5

对于 (G)，我们有一个贪心的思路：对于一个结点 (x)，若它的子结点中有 (c) 个还是可用的，那么分 (c) 奇偶性讨论：

一句话概括，就是子结点尽量连深度大的。正确性？设 (x) 的父结点为 (f)，如果我们不将在深处连反而连向更浅的 (f)，那么边 ((f, x)) 会经过两次以上，而原来的算法每条边只占用一次，毫无疑问更劣了，对于 (f) 的祖先更是如此。于是乎这个贪心就是正确的。

对于 (c) 的奇偶性，可以通过子结点子树大小的奇偶性判断。

对于 (B)，显而易见我们需要最大化每条边被经过的次数。对于一条边，如何求得其最多可被经过的次数呢？我们不妨断开此边，得到来两个连通块，大小分别为 (u, v)，那么经过的路径数为 (min(u, v))。比如边 ((fa_x, x))，路径数即为 (min(size_x, 2k-size_x))。

最后两次 Dfs 即可，复杂度 (O(k))。

「AtCoder AGC018D」Tree and Hamilton Path

update - 2020.8.6

神仙贪心树论题。

根据哈密顿路径的定义，每个点必须经过一次。但这里直接求非常不好处理，不妨我们计算边的贡献。

对于权为 (v) 的一个边，若有 (k) 条路径经过它，那么其贡献为 (k imes v)。假设断开此边，得到两个大小分别为 (u, v) 的连通块，那么会有 (min(u, v) imes 2) 条路径经过此边。因为对于较小的连通块，其中每个点出发的路径长要尽可能大，那么显然必须跨越这条边。

这些贡献的和不难一次 Dfs 求出，但问题是现在所求得的是哈密顿回路。怎么办？只要额外减去一条路径即可。但我们显然不能直接剪掉最小的，起码是最优解集中的。

一个可能并不显然的贪心结论：最优解集中的所有路径必定经过重心。简单说明一下：根据重心的性质，以重心为根的树，其所有子树的 (size < n/2)。对于一个非重心结点而言，其子树中一定有一条不经过该点的路径。因为其他所有子树的结点加起来都不够这颗子树的结点配对的，那么只能自己配对自己。

于是可以直接把重心周围一条最小的边减去即可。不过重心可能会有两个，那只要减掉两重心的连边。

时间复杂度 (O(n))。

「APIO2010」巡逻

update - 2020.8.6

由题意得不加边时总路程为 (2n)。

首先考虑 (k = 1) 的情况。当加上一条边时会构成一个环。设连边 ((u_1, u_m)) 后构成环 ( ext{R} = {u_1, u_2, cdots, u_m})，那么整个环上的边只会走一遍。我们需要最大化环的长度，那么只需要求一次直径（长度记为 (L)）即可。答案为 (2(n-1) - L + 1)。30 pts 到手。

然后是 (k = 2) 的情况。基于上述方法，我们加边之后会得到一个环 ( ext{R})。若再次加边又有一个环 ( ext{R}^prime)，如果不重合那么好办，着重考虑这两个环的重合时如何处理。

对于一条边 (e)，显然有：

若 (e in ( ext Rcap ext R^prime))，即两个环都经过了 (e)，那么 (e) 会被走两次。
若 (e otin ( ext Rcup ext R^prime))，即两个环都不包含 (e)，那么 (e) 也会被走两次。
否则，(e) 只属于一个环，那么只会走一次。

比较清晰了，我们可以先求一次原树直径，长度为 (L_1)。然后再将直径上的所有边置为 (-1)（原为 (1)）。再在新树上跑一边直径，长为 (L_2)。最后答案为 (2(n-2)-L_1-L_2+2)。

由于第一次需要求出整个直径，要两次搜索；第二次有负权，要树形 dp。

时间复杂度为 (O(n))。

「UVA 1464」Traffic Real Time Query System

update - 2020.8.7

题目中要求两点见必须经过的点有几个，那么就是割点的个数。

首先用 Tarjan 算法进行 v-BCC（点双连通分量）缩点，我们会得到一颗树。

根据缩点的方式，不难发现一条路径上的点的排列规律为『v-BCC，割点，v-BCC，割点，v-BCC……』

于是答案为『求路径上深度为偶（奇）数的』

设边 (s, t) 所在 v-BCC 的编号为 (x, y)，那么答案就是 (frac{1}{2}( ext{dep}(x)+ ext{dep}(y)- ext{dep}( ext{LCA}(x, y))+1))。

时间复杂度（LCA 使用树剖实现）(O(n+m+qlog n))。当然若优化 LCA 的过程可以得到更优秀的线性复杂度。

「POJ 2942」Knights of the Round Table

update - 2020.8.7

根据题中所给的条件，可以建出一个无向图，若骑士 (u, v) 互相憎恨，那么就会有一条 (u leftrightarrow v) 边。为了方便处理，我们需要的是原图的反图，若两骑士可以相邻，那么其间会有连边。

那么题目就转化为『求有几个结点不属于任何一个奇环』。由于一个环必然是一个 v-BCC（点双连通分量），因此可以先用 tarjan 算法求出所有 v-BCC。不难发现，合法的点必定在 v-BCC 中。

对于一个 v-BCC，若存在一个奇环，那么整个 v-BCC 合法，否则整个不合法。下面给出简单的证明：

设 v-BCC 中有一个奇环，长度为 (t)，并有 v-BCC 中的环外一点 (k)。根据双连通性，从 (k) 出发一定存在（除顶点 (k)）两条不相交的路径，终点为奇环上的某两点。这样原来的奇环分为两部分，长度分别为 (x, t-x)。设从 (k) 出发的两条路径构造出的新部分长为 (y)，于是结点 (z) 在长度为 (x+y, t-x+y) 的两个环中。由于 (t) 为奇数，所以 (x, t-x) 奇偶性不同，那么 (x+y, t-x+y) 奇偶性也不同，说明 (z) 在两个奇偶性不同的两个环内，总有一个是奇环。于是得证。

那么怎么判断一个子图中存不存在奇环呢？众所周知，二分图不存在奇环，那么这个问题就相当于二分图的判定。我们可以使用一种黑白染色的方法，如果相同颜色的两点间存在连边，那么就不是二分图。

此题可在 (O(Tn^2))（(T) 为数据组数）的时间内通过，代码细节很多，~~点双真的难写~~。

「Aizu 2991」XORANDORBAN

update - 2020.8.10

如果 (a operatorname{and} b = A, a operatorname{or} b = O, a operatorname{xor} b = X) 三者其一成立，那么如果选择 (a) 就不能选择 (b)，反之亦然，即 (a o eg b,b o eg a)。

那么典型就是一个 2-SAT 问题。对于所有 (ain [0, 2^{N+1}))，加入条件 (a o eg (aoperatorname{xor} X),(aoperatorname{xor} X) o eg a)。但是对于 ( ext{ans, or}) 却不能这样处理——它们不像异或有逆运算。

暴力两重循环枚举？(O(2^{2(N+1)})) 似乎不是很可以。我们设全集为 (U = {0, 1, cdots, 2^{N+1}-1})，那么对于当前枚举到的集合 (I)，我们希望找出所有满足 (Icap J = A) 的集合 (J)，当然若 (I otsubseteq A) 那么也无需考虑了。那么只要枚举 (I) 的补集 (complement I) 的子集即可。

对于 ( ext{or})，也只需要枚举 (I) 的子集（在 (O subseteq I) 的条件下）就行了。

最后建完图跑一边 Tarjan 即可。

「TJOI2019」大中锋的游乐场

update - 2020.8.10

发现就是比 naive 最短路加上了一维，于是第一感觉是 (dist(x, p, q)) 表示到达点 (x)，吃了 (p) 个汉堡，喝了 (q) 瓶可乐的最短距离，然后分层图最短路跑一遍。

这样子显然爆炸，但我们发现只有汉堡、可乐个数的个数之差 (|p-q|) 相同的状态本质相同，多设不如设一个，那么考虑设 (dist(x, s)) 为当前到 (x)，汉堡个数减去可乐个数的值为 (s)，显而易见 (|s|le k) 的状态才是合法的。

一看 (kle 10)，那么状态总数在一个可接受的范围内。Dijkstra 一边走掉，复杂度 (O(k(n+m)log (km)))（STL）。

后记

原文地址：https://www.cnblogs.com/-Wallace-/p/13433671.html
本文作者：@-Wallace-
转载请附上出处。