图论杂题选讲.md

图论杂题选讲

讲师：PinkRabbit 时间：20210629 地点：福建师范大学附属中学

Example.1 Jump

题意：

在数轴上有 $n$ 个跳跃重心 $a_1,a_2,…,a_n$。

你每次可以选择一个跳跃重心，跳到当前位置关于它对称的地方去。

$q$ 次询问，每次给出起点 $s$ 和终点 $t$，询问从起点到终点最少需要跳多少步，无解输出 $-1$。

数据范围：$1≤n≤200$，$0≤a_i,s,t≤10^4$，$1≤q≤10^5$。

题解：

对于“对称”类型的题目，我们可以直接把对称公式写出来： $$ pos=\left(2a_{p_k}-\left(2a_{p_{k-1}}-\cdots(2a_1-start)\right)\right)=2\sum_{i=1}^k(-1)^{k-i}a_{p_i}+(-1)^k\cdot start $$ 直接枚举 $k$ 的奇偶性，然后前半部分总的做一次最短路；显然只要求出 $0$ 到 $[-2v,2v]$ 之间的单源最短路即可。

Example.2 Today is a rainy day

题意：

给定两个数字串 $s$ 和 $t$，长度均为 $n$，且仅包含数字 $123456$。

你每次可以进行下面两种操作：

1.修改串的某一位。

2.选定两个数字 $x,y$($1≤x,y≤6$)，把串中所有数字等于 x 都改为 y。

求把 $s$ 改成 $t$ 的最小步数。数据范围：$1≤n≤100$。

题解：

注意到，单点修改是具有支配性的，对于一种最有情况下的单点修改，我完全可以直接把它放到最后做直接把他更改为答案！

所以，得出一定是先进行 2 操作再进行 1 操作；由于数字种类有限，因此 $2$ 操作的综合效果只有 $6^6$ 种（每个数字映射到另一个数字）；对于每种结果，进行一次逐位比较即可。

Example.3 Walk

题意：

给定一张 $n$ 个点的有向图，点 $i$ 的权值是 $val_i$，若 $val_i$ and $val_j=val_j$，则 $i$ 向 $j$ 连单向边。

另外再给定 $m$ 条有向边，求 $1$ 号点到每个点的最短路。

数据范围：$n≤2×10^5$，$m≤3×10^5$，$0≤val_i<2^{20}$。

题解：

核心问题在于如何优化建图。考虑对于每个 $val$ 的值都新建一个虚点，在虚点间优化连边。

第一种连边方式是按照 fmt 的方法来分治地连边；第二种就是每个点 $v$，只向大小为 $|v|+1$ 的点集连边。

这些虚边的边权都是 $0$；虚边连向点的边也都是 $0$；点连向虚边的边权是 $1$。进行一次 01 bfs 即可。

Example.4 树上传送

题意：

给定一棵树，$i$ 号点可以花费 $v_i$ 的代价，传送到距离不超过 $d_i$ 的点去。

求 $1$ 号点到每个点的最短路。

题解：

利用点分树优化建图；不需要容斥，因为重复连边不影响答案。

于是乎，每个点实际上只是向点分树上它到根的这一条链上的每个点，它的周围的一圈进行连边。

单独看这一圈的连边，这很容易，直接一圈一圈的前缀和地连就是对的（边数 $O(n\log n)$）。

Example.5 Travel

题意：

给定一张 $n$ 个点的完全图，其中 $m$ 条边的权值为 $a$，其余的为 $b$，给定这 $m$ 条边，求从 $1$ 到 $n$ 的最短路。

数据范围：$n≤10^5$，$m≤5×10^5$。

题解：

如果 $a&gt;b$：

如果 $1$ 和 $n$ 之间是一条 $b$，就直接走一条 $b$；如果 $1$ 和 $n$ 之间是一条 $a$，我要试图找到一条比 $a$ 短的，我一条 $a$ 都不能走，直接在 $b$ 构成的图上 bfs 最短路即可。

如果 $a&lt;b$：

如果 $1$ 和 $n$ 之间是一条 $a$，就直接走一条 $a$；如果 $1$ 和 $n$ 之间是一条 $b$，我要试图找到一条比 $b$ 短的，我一条 $b$ 都不能走，直接在 $a$ 构成的图上 bfs 最短路即可。

对于第一种中的 bfs 是一种补图 bfs ，要怎么做呢？

用链表维护尚未到达的点，然后转移的时候暴力扫链表、遇到没删除的边就删掉对应的点，这样做总复杂度是线性的。

Example.6 Kirakira

题意：

对于给定的 $n$，有函数 $f(x)=\sum_{i=1}^n x \bmod i$。

对于所有 $i≥1$，结点 $i$ 连单向边到 $f(i)$。

求这个无限图中的最长环长。数据范围：n≤10000。

显然有： $$ f(x)\le \sum_{i=1}^ni $$ 因此我们只需要快速求出前 $5\times 10^7$ 个 $f$ 然后找环即可；如何快速求 $f$？ $$ f(x)=xn-\sum_{i=1}^ni\left[\frac xi\right]=xn-g[i] $$ 由于 $\left[\frac xi\right]$ 仅仅在 $i$ 的倍数处增长，因此易得： $$ g[n]=\sum_{i=1}^n\sigma_1(i) $$

Example.7 新年的繁荣

题意：

给定一张 $n$ 个点的完全图，每个点有权值 $a_i$，$(i,j)$ 边权为 $v_i \and v_j$。

求最大生成树。数据范围：$n≤10^5$，$0≤a_i<2^m$，$m≤18$。

题解：

Boruvka 的思想在于，每层进行 $Poly(n)$ 次操作，将连通块数量减少至少一半，来保证总的复杂度。

考虑这题中如何完成每层中的寻找每个连通块向外最大连边的操作？

比较常见的方法是，将所有的点都加入一颗 Trie 中；扫到一个连通块时，暴力将其中发每个点都从 Trie 树上剔除，然后每个点在 Trie 树中查询；但是这题中这个做法不太行。

考虑进行一次下标为 $v$、值为 $v$ 所在连通块编号的最小值和最大值的 fmt。（重要方法）

查询 $v$ 在其他连通块的最大匹配时，贪心地一位位去试，比如 $v=(10110)_2$ 时，先看一下 $f[2^4]$，如果可以的话看一下 $f[2^4+2^2]$；如果不行的话看一下 $f[2^4+2^1]$ ……

Example.8 病毒实验

题意：

一个 $r×c$ 的网格图，每个格子有一个权值 $u_{i,j}$，也有障碍物（$u_{i,j}=0$）。

有一个循环长度为 $m$ 的无限循环序列 $d$，只包含 LRUD 四种字符。

假设初始时有某一个非障碍物格子被激活了。

对于一个没被激活的非障碍物格子，如果 $d$ 中存在一个连续 $u_{i,j}$ 长度的子串，使得这个格子对应方向上的格子（不能是障碍物）都被激活了，那么它也会被激活。这可能继续连锁反应下去，则最终可能会有很多其他格子被激活。

请求出：假设初始时它被激活了，最终被激活的格子数量最少可能是多少。以及有多少种初始格子能达到这个最小值。

数据范围：$r,c≤800$，$m≤10^5$。

题解：

重要方法：关键点合并法（草）

首先可以先预处理出每个点被感染的条件（东南西北哪些要被感染）。因为东南西北向的一共只有 $16$ 种，因此可以预先枚举并处理。

一开始，如果 $A$ 可达 $B$，你会发现 $A$ 一定不会优于 $B$，于是我就可以把 $A$ 加入 $B$ 的势力范围；称 $B$ 为这个势力范围的关键点。

考虑如何合并势力范围——从当前势力范围的关键点开始广搜，一旦到达另一个势力范围，那么就把当前势力范围合并过去，并删除当前关键点。

为什么是对的呢？因为按照此方法合并关键点有这些性质：势力范围中每个点均可抵达关键点，但是关键点不一定能到达整个势力范围；关键点的可达集就是可选的初始点的集合，必要是因为势力之内的点均可抵达关键点，选了关键点不可达的一定不优；充分性显然。或者说，关键点的可达点集是与自身等价的点构成的点集。

因此我们就可以完成 Buruvka 的快速合并——从每个关键点广搜出去，一出去就删除当前关键点、完成合并。

最后的第二个答案就等于第一个答案乘以能能达到第一个答案的关键点数量。$O(rc\log)$。

Example.9 白金元首与独舞

题意：

给定一个 $n$ 行 $m$ 列的网格，每个格子有一个上下左右的箭头或未填。

请计算所有满足从每个格子出发按照箭头方向移动最终都能走出网格的填法方案数，模 $998244353$。

数据范围：$n,m≤200$，未填的格子数量 $≤300$。

题解：

复习一下 Matrix-tree 定理：

一张图的生成树个数等于其基尔霍夫矩阵的 $n-1$ 阶主子式的行列式。

拓展为有向树版本：

$u\rightarrow v$，a[u][v]++。

外向树：v++。

内向树：u++。

$s$ 为根：去掉第 $s$ 阶即可。

拓展为带重边版本：

……的行列式为每棵树的边权乘积的和

拓展为加法版本：

将每条边的权值定为 $1+a_ix$，然后进行 $\bmod x^2$ 意义下的高斯消元，最后输出一次项即可。

这题直接连通分量缩点完跑外向树的 Matrix-tree 即可。

Example.10 Expection

题意：

给定一张 $n$ 个点 $m$ 条边的无向连通图，每条边有两个权值 $a,b$，求以 $a$ 建出来的最小生成树的权值 $b$ 的和的期望（每棵树中均匀随机）。

模 998244353。

数据范围：$n≤10^5$，$m≤2×10^5$，相同的 a 的数量不超过 30。

题解：

最小生成树计数类问题，一般来说是在 kruscal 的过程中运用 Matrix-tree 定理。

对于三十种不同的权值，每次同时加入图中，把图分成了若干个连通块，每个连通块会被连出一个生成树；连出完直接缩为一个点。

由于这颗树种均匀随机，所以每个连通块不会太大，因此这么做复杂度大概是对的（？）

注意本题中需要进行两次，一次是 $0$ 次的，一次是关于 $b$ 一次的。

Example.11 生成树

题意：

给定一张 $n$ 个点的无向图，每条边有红绿蓝三种颜色。

求绿边数量不超过 $g$，蓝边数量不超过 $b$ 的生成树数量，模 $998244353$。

数据范围：$n≤40$。

题解：

直接上二元生成函数，然后把前 $x^g\cdot y^b$ 插值出来（注意，需要 $gb$ 个点值）。复杂度 $O(\frac 18n^6)$。

Example.12 生成树计数

题意：

给定一张 $n$ 个点的带权无向完全图，求所有生成树权值的 $k$ 次方之和，生成树权值定义为边权和，模 $998244353$。

数据范围：$n≤30$，$0≤k≤30$。

题解：

一般来说，$k$ 次方和类型的问题都使用如下的方法： $$ a^k=k![x^k]e^{ax} $$

$$ \left(\sum_{i=1}^na_i\right)^k=k![x^k]e^{(\sum a_i)x}=k![x^k]\prod_{i=1}^ne^{a_ix} $$

于是我们只要维护一个 $\bmod x^{k+1}$ 的行列式即可；但是众所周知这不太合适。

考虑使用插值——这个行列式是 $n(k+1)$ 的，我们只要带入这么多的值，最后直接把答案插出来。

Example.13 C4

题意：

求长度为 $4$ 的环的固定起点的欧拉回路数量，对 $998244353$ 取模。

环中每条边是无向边，边上有边权表示这条边应该被经过的次数。

数据范围：$1≤value≤5×10^5$。

题解：

先讲普通有向图的情况：欧拉图，即每个点入度等于出度且连通的图。一张图存在欧拉回路和它是欧拉图等价。

对于一张欧拉图，它的欧拉回路个数为： $$ T_s\prod_{i=1}^n(deg_i-1)! $$ 其中 $T_s$ 为以任意一点为根的外向树个数。

回过头来看这题——加入我们枚举一条边的一个方向的经过次数，我们可以推出每条边的每个方向的经过次数；然后就可以转换成普通的有向图欧拉回路的求法。$O(value\cdot n^3)$。

Example.14 Binary Code

题意：

给定 $n$ 个 01 字符串，每个字符串可能有一位变成了 ?。

请给每个 ? 确定变成 0 或 1，使得最终不存在两个串满足其中一个是另一个的前缀。请输出一种可行方案。

数据范围：总串长 ≤ 5×10^5。

题解：

建一个 Trie 树，把每个串的两种情况对应的点在树中的点，作为 2-SAT 中的两个互斥的决策。

把每个父节点连向子树中每一个节点，表示前缀的矛盾，然后就直接跑 2-SAT 即可。

Example.15 Flag

题意：

数轴上有 $n$ 对点 $(x_i,y_i)$，请从每对点中选出一个，最大化选出的点之间距离的最小值。

数据范围：$n≤10^4$。

题解：

外层先二分；内层的判定像是一个 2-SAT 问题，直接线段树优化建图即可。

Example.16 LYZ

题意：

有鞋码为 $1∼n$ 的鞋子各 $k$ 双，共 $nk$ 双。

脚长为 $x$ 的人可以穿鞋码在 $[x,x+d]$ 内的鞋子。

$q$ 次操作，每次给出 $(r,x)$ 表示脚长为 $r$ 的人增加了 $x$ 个（如果 $x$ 为负数表示减少）。

请动态维护每次操作结束后是否可以给这些人分配鞋子。

数据范围：$n≤2×10^5$，$q≤5×10^5$，$1≤r≤n-d$。

题解：

完美匹配存在性判定请认准 Hall 定理:

一个二分图存在完美匹配等价于对于左部点集的任何一个子集 $S$ 与它的邻集 $T$ 都有 $|S|\le |T|$。

这题中也使用这个定理。下面是另一个引理：

本题中，Hall 定理等价为左部的任意一个区间 $S$ 与它的邻集 $T$ 都有 $|S| \le |T|$。

证明：如果存在一组 $S$ 和 $T$ 满足 $|S|&gt;|T|$，那么一定存在一个 $T'\subseteq T$ 使得 $T'$ 是 $T$ 的一个子区间且 $|S'|&gt;|T'|$（如果不存在的话，那么合起来也不会存在）因此我只需考虑连续的 $T$。 为了尽可能地判断它不行，我要最小化 $|T|-|S|$，于是对于同一个区间 $T$，我当然选取一个极大的 $S$ ——会对应为一个区间。证毕。

于是问题就成了判断是否存在区间 $[l,r]$ 满足： $$ \sum_{i=l}^ra_i>(r+d-l+1)\cdot k $$ 转化为查询如下的最小值是否小于 $0$： $$ \sum_{i=l}^r(a_i-k)-dk $$ 用线段树维护最小区间即可。

Example.17 Rooms

题意：

给定一个由小写字母组成的 $n×m$ 的矩阵，定义一个房间是同字母的极大四连通块。

$q$ 次询问，每次给出一个矩形，问有多少房间与矩形有交。

数据范围：$n,m≤2000$，$q≤5000$。

题解：

为每个矩形随便找一个关键点，代表这个连通块。

先二维偏序计算矩形中有多少个关键点；然后考虑如何统计关键点不在矩形中的相交连通块——直接 $O(n)$ 扫描边界即可。

Example.18 Xor-matic Number of the Graph

题意：

给定一张 $n$ 个点 $m$ 条边的无向图，边有非负整数边权。

请求出所有满足 $u$ 和 $v$ 之间存在一条异或和为 $w$ 的路径且 $u&lt;v$ 的三元组 $(u,v,w)$ 的 $w$ 之和。

数据范围：$n≤10^5$，$m≤2×10^5$，边权 $≤10^{18}$。

题解：

分成每个联通分量来考虑。

联通分量中的每一个环都是都是可以自由算入答案的（走到环、绕一圈、原路返回，就能凭空把环算入答案）。

我们将连通块中所有本质不同的环加入线性基 $B$（本质不同的环直接在任意一颗生成树中，每条非树边分别对应一条本质不同的环），并记这颗树中点 $u$ 到根的异或和为 $d_u$。

于是 $u$ 与 $v$ 之间的答案集合为 $d_u \oplus d_v\oplus B$。

考虑按位统计答案——考虑线性基的性质，若一位上存在 $1$，那么恰有 $2^{|S|-1}$ 这一位为 $1$ 的数；如果全部为 $0$，那么全部 $2^{|S|}$ 个数这一位上均为 $0$。

然后考虑如何枚举 $u$ 和 $v$ ：也直接按位考虑即可，一位位枚举，如果 $B$ 的一位上存在 $1$，那么 $u$ 和 $v$ 任取都恰有一半的数这一位为 $1$；如果不存在，那么 $u$ 和 $v$ 要恰有一个这一位为 $1$，若记这一为上为 $1$ 的 $d$ 有 $x$，那么这一位的贡献次数为 $x(n-x)$。

Example.19 Bajtocja

题意：

给定 $d$ 张无向图，每张图都有 $n$ 个点，初始时没有边。

接下来 $m$ 次操作，每次操作给定 $(k,a,b)$，在第 $k$ 张图中连边 $(a,b)$。

每次操作后输出点对 $(u,v)$ 的数量，满足 $u,v$ 在每张图中都是连通的。

数据范围：$d≤2000$，$n≤5000$，$m≤10^6$。

题解：

Hash 妙妙题。

对于每个点记录一个序列 $A$，表示它在每张图中位于的联通块编号。易见，两个点能联通的充要条件是，两个点的 $A$ 序列相同。

因此我们把 $A$ 拿去 hash 起来，拿个桶存一下。修改的时候如何维护 hash(A) 呢？我们只修改小的那个集合的 Hash 即可，根据启发式合并，这么做是对的。

Example.20 Rally

题意：

给定一张 $n$ 个点 $m$ 条边的 DAG，每条边长度为 $1$。

你可以删除一个点，最小化删除后的最长路径长度。

数据范围：$2≤n≤5×10^5$，$m≤10^6$。

题解：

首先将它拓扑排序一下，压成一个序列上的问题。所有的边都是从左往右连。

为了简化问题，建一个虚原点和虚汇点。

删除一个点，意味着要经过一条横跨它的边，才能到达虚汇点。因此我们可以预处理 $dis(s,l)$ 和 $dis(r,t)$，然后枚举这条横跨边，快速计算它的路径长度。

提前算出每条边对应的 $dis(s,l)+dis(r,t)+1$，然后就是一个二维偏序问题了。

Example.21 Tournament cycle

题意：

求有多少个 $n$ 个点的竞赛图存在长度为 $k$ 的环。

数据范围：$n,k≤5000$。

题解：

竞赛图的一个性质：

一个大小为 $x$ 的强连通竞赛图，一定存在大小为 $1\sim x$ 的环。

这题中，用总数 $2^{\frac {n(n-1)}2}$ 减去不存在的个数；不存在就等价于不存在大小大于等于 $k$ 的强连通分量。

如何计数呢？设 $f[n]$ 表示 $n$ 个点的不存在……的个数；$g[n]$ 表示单个强连通分量的计数。于是有： $$ f[n]=\sum_{i=1}^{k-1}g[i]\cdot f[n-i]\cdot\pmatrix{n\i} $$

$$ g[n]=2^{\pmatrix{n\2}}-f[n]\ \ \ (n\le k) $$

毕竟这个式子只需要用到 $\le k$ 的 $g$。