图论杂题选讲

讲师：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.修改串的某一位。
$x,y$ $1≤x,y≤6$ )，把串中所有数字等于 x 都改为 y。
$s$ $t$ $1≤n≤100$ 。

题解：

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

$2$ $6^6$ 种（每个数字映射到另一个数字）；对于每种结果，进行一次逐位比较即可。

Example.3 Walk

题意：

$n$ $i$ $val_i$ $val_i$ $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>b$ ：

$1$ $n$ $b$ $b$ $1$ $n$ $a$ $a$ $a$ $b$ 构成的图上 bfs 最短路即可。

$a<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|>|T|$ $T'\subseteq T$ $T'$ $T$ $|S'|>|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<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$ 。