来自xhb课件的一些图论题

最短路

LG P3403 跳楼机

Description

楼高为HH ,初始位于 11 楼,每次可以向上移动 x/y/zx/y/z 楼,问能到达的楼层数

Solution

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

f[i]f[i]表示能到达的最小的,模xx意义下为ii的楼层

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

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

Summary

同余最短路

51nod1693 水群

Description

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

Solution

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

建图最短路,直观想法是iii×ki\times k连边,向i1i-1连边。考虑优化:

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

BZOJ4289 Tax

Description

给出一个nn个点mm条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值

求从起点11到点nn的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权

n105,m2×105n\le 10^5, m\le 2\times10^5

Solution

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

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

对于一个原图中的点而言,设新图中连进它的边集为SS,从它连出去的边集为TT

不难发现,这里的SSTT是一一对应的(有向边是由无向边拆得)

S,TS, T按边权从小到大排序,连边方法:(Si,Ti,wi),(Ti,Ti+1,wi+1wi),(Ti+1,Ti,0)(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

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

n,m105n, m\le 10^5

Solution

很奥妙重重的一道题

aia_i表示未加边前11ii的最短路,bib_i表示22ii的最短路,did_i表示ii和新加点之间的边权

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

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

d1+diaid2+dibi \begin{aligned} d_1 + d_i \ge a_i\\ d_2 + d_i \ge b_i \end{aligned}

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

换句话来说,还有可能aj+dj+di<aia_j + d_j + d_i < a_i

但是,我们只需要满足aj+djd1a_j + d_j \ge d_1即可,因为d1+did_1 + d_i就已经比aia_i大了(自认为讲得比较清楚),即

di+aid1di+bid2 \begin{aligned} d_i + a_i \ge d_1\\ d_i + b_i \ge d_2 \end{aligned}

综上,需要满足

dimax{d1ai,d2bi} d_i\ge \max\{|d_1 - a_i|, |d_2 - b_i|\}

因为要求di\sum d_i尽量小,所以当d1,d2d_1, d_2确定时,取等号最优

问题转化为:确定d1,d2d_1, d_2,使i=1n{d1ai,d2bi}\displaystyle \sum_{i=1}^{n}\{|d_1 - a_i|, |d_2 - b_i|\}最小

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

生成树

CF125E

直接wqs二分即可

CF888G

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

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

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

分层图

BJWC2012 冻结

sbt,f[i][j]f[i][j]表示到ii,用了jj次,直接跑最短路

CF1137C Museums Tour

Description

一张nn个点mm条边的有向图,定义周期为 dd 天,从第一个周期的第 11 天开始从 11 号点出发,一条边耗时一天。

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

n,m105,d50n, m\le10^5, d\le 50

Solution

注意到dd很小,于是可以往分层图上想

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

缩点后求最长路即可

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

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

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

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

强连通分量

BZOJ2438 杀人游戏

Description

nn 个人,其中有一个杀手。有mm条认识关系(x,y)(x, y),表示xx能确定确定yy是平民还是杀手

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

n,m3×105n, m\le 3\times10^5

Solution

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

缩点后求入度为00的点数即可

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

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