图论复习

QQ：916591630

1. 升降梯（HF主域 B1213）

解析

考点：建图。

将电梯层数和手柄所在位置打包成一个点，用dis[i][j]表示到达第i层且手柄在位置j的最短时间。

对于点 $(i,j)$，向点 $(i+C_j,j)$ 连边权为 $2C_j$ 的单向边，向点 $(i,j-1)$ 和 $(i,j+1)$ 连边权为 $1$ 的双向边。

输出$\min(\mathit{dis}[N][j])$ 。

2. POJ3635

题面

有 $N$ 个城市和 $M$ 条道路。仅城市内有加油站，不同城市的加油站价格不同（加油只能加整数升，城市间道路的油耗也是整数升）。计算：一架油箱容量为 $C$ 的车，从 $S$ 开到 $T$ 至少要花多少油钱？

数据范围：$N \leq 10^3,M \leq 10^4,C \leq 100$。

解析

用f[i][j]表示到达城市i，还剩j升汽油的最小花费。

对于点 $(i,j)$，向 $(i,j+1)$ 和 $(k,j-\mathit{dis}[i][k])$（i->k有边）连边。

建图后跑Dij即可。

3. 道路与航线（P3008）

解析

注意到航线可以将全图割裂为若干部分，将这些部分视作若干个点，航线为连接这些点的边。

先在每部分内跑spfa，再在全图跑spfa。

4. POJ3463

题面

给出一个无边权有向图、源点、终点，求出源点到终点的最短路径条数和比最短路径长度大 $1$ 的路径条数。

解析

d[i][0],f[i][0]表示起点到i的最短路权值和条数。

d[i][1],f[i][1]表示起点到i的次短路权值和条数。

套用Dij，更新时分四种情况：

• $d[x][k]+z=d[y][0]$ => $f[y][0]+=f[x][k]$
• $d[x][k]+z=d[y][1]$ => $f[y][1]+=f[x][k]$
• $d[x][k]+z<d[y][0]$ => $ d[y][1]=d[y][0], f[y][1]=f[y][0], d[y][0]=d[x][k]+z,f[y][0]=f[x][k] $
• $d[y][0]<d[x][k]+z<d[y][1]$ => $d[y][1]=d[x][k]+z, f[y][1]=f[x][k]$

5. POJ2449：第k短路

题面

给定有向图，输出第 $k$ 短路的长度。

解析

考点：A*算法

设计估价函数，函数值不劣于最优值，此时算法一定正确。

估价越接近最优值，效率越高；估价为 $0$时，退化为普通搜索。

在反图上求出所有点到终点的最短路径。

估价函数：当前走过的距离+该店到终点的最短路长度。

用优先队列维护，每次取出估价函数值最小的一个点扩展。

第几次从优先队列中取出点u，就是找到了u的第几短路。