「笔记」一些图论题

[Summary]

来自xhb课件的一些图论题

最短路

LG P3403 跳楼机

Description

楼高为$H$ ，初始位于 $1$ 楼，每次可以向上移动 $x/y/z$ 楼，问能到达的楼层数

Solution

[最短路]

去掉一个限制，考虑在模$x$意义下，只通过走$y/z$步能到达的楼层

设$f[i]$表示能到达的最小的，模$x$意义下为$i$的楼层

$f[i] + y \rightarrow f[(i + y)\%x],f[i] + z \rightarrow f[(i + z)\%x]$

跑最短路即可，答案就是$\displaystyle \sum_{i=0}^{x-1}\lfloor\frac{H-f[i]}{x}\rfloor + 1$

Summary

同余最短路

51nod1693 水群

Description

初始有$1$ 个表情，每次可以复制所有/退一格/粘贴，问达到 $n$ 个表情的最小操作数

Solution

[最短路]

不难发现过程一定是一次复制后多次粘贴，再多次退格

建图最短路，直观想法是$i$向$i\times k$连边，向$i-1$连边。考虑优化：

• 当$k$为和数的时候显然可以拆成质数的积，所以$k$只需要枚举质数
• 不会利用到$k>11$的边

BZOJ4289 Tax

Description

给出一个$n$个点$m$条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值

求从起点$1$到点$n$的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权

$n\le 10^5, m\le 2\times10^5$

Solution

[最短路]

把一条边拆成两条有向边，再把有向边视为点，然后按题意建图

直接建图边数是$O(m^2)$的，考虑优化

对于一个原图中的点而言，设新图中连进它的边集为$S$，从它连出去的边集为$T$

不难发现，这里的$S$和$T$是一一对应的（有向边是由无向边拆得）

将$S, T$按边权从小到大排序，连边方法：$(S_i, T_i, w_{i}), (T_i, T_{i+1}, w_{i+1} - w_i), (T_{i + 1}, T_{i}, 0)$

正确性显然，是一个经典套路

GZOI2019 旅行者

BZOJ4061 Farm and factory

Description

给定一个$n$个点$m$条边的无向图。现要新加入一个点，这个点与$n$点分别连了一条边。需要设定这$n$条边的边权（可为实数），满足$n$个点到$1, 2$号点的最短路不一定经过这个新点，并且这$n$条边的边权平均值最小

$n, m\le 10^5$

Solution

[曼哈顿与切比雪夫距离] [最短路]

很奥妙重重的一道题

设$a_i$表示未加边前$1$到$i$的最短路，$b_i$表示$2$到$i$的最短路，$d_i$表示$i$和新加点之间的边权

以下内容画图可能会更加清楚

首先，为了保证合法，必须要满足

$\begin{aligned} d_1 + d_i \ge a_i\\ d_2 + d_i \ge b_i \end{aligned}$

此时这个界并不紧，因为到$i$的最短路还有可能先经过另外一个点$j$，再经过新加点，再到$i$

换句话来说，还有可能$a_j + d_j + d_i < a_i$

但是，我们只需要满足$a_j + d_j \ge d_1$即可，因为$d_1 + d_i$就已经比$a_i$大了（自认为讲得比较清楚），即

$\begin{aligned} d_i + a_i \ge d_1\\ d_i + b_i \ge d_2 \end{aligned}$

综上，需要满足

$d_i\ge \max\{|d_1 - a_i|, |d_2 - b_i|\}$

因为要求$\sum d_i$尽量小，所以当$d_1, d_2$确定时，取等号最优

问题转化为：确定$d_1, d_2$，使$\displaystyle \sum_{i=1}^{n}\{|d_1 - a_i|, |d_2 - b_i|\}$最小

发现是个切比雪夫，可以转成曼哈顿，然后分别对$x, y$坐标取中位数即可

生成树

CF125E

直接wqs二分即可

CF888G

最小异或生成树，在这里已经写得很清楚了

上次是抄的代码。。。这次自己写了下

之前的代码还没有类似启发式合并地查找，就是每次用元素少的集合丢到元素多的集合里查

分层图

BJWC2012 冻结

sbt，$f[i][j]$表示到$i$，用了$j$次，直接跑最短路

CF1137C Museums Tour

Description

一张$n$个点$m$条边的有向图，定义周期为 $d$ 天，从第一个周期的第 $1$ 天开始从 $1$ 号点出发，一条边耗时一天。

点在每个周期中会有部分时间有 $1$ 的点权，同一点不能重复获得点权，问能够得到的最大价值。

$n, m\le10^5, d\le 50$

Solution

[强连通分量] [缩点]

注意到$d$很小，于是可以往分层图上想

按天分层，对于原图中$x\rightarrow y$的边，连$(x, k) \rightarrow (y, k + 1)$的边（注意不用真的连出来）

缩点后求最长路即可

这里缩完点后每个新点的$size$并不是直接把它包含的所有点的权值加起来，因为可能有点重复的情况，要用个vis搞下

为什么每个点只会被算一次贡献？

即若$(x, k)$能走到$(x, k')$，那么它们为什么一定在同一个强连通分量中？

显然，考虑从$(x, k)$到$(x, k')$经过的路径序列，把它再重复$d-1$次后，一定能回到$(x, k)$

强连通分量

BZOJ2438 杀人游戏

Description

$n$ 个人，其中有一个杀手。有$m$条认识关系$(x, y)$，表示$x$能确定确定$y$是平民还是杀手

警察需要选择一些人查证，选到杀手就会被杀掉，问确认杀手之前不被杀死的概率最大是多少

$n, m\le 3\times10^5$

Solution

[强连通分量] [缩点]

题意就是要确定每个人的身份。假设最优解中最少要查询$k$个人，那么答案就是$1 - \frac{k}{n}$（这$k$个人每个人有$\frac{1}{n}$的概率是杀手）

缩点后求入度为$0$的点数即可

若缩点后存在一个大小为$1$，入度为$0$的点，并且它所有指向的点均能被其他某些点到达，那么ans--

因为最后只剩这个点的话，就知道他是不是凶手了