NOIP2024集训Day53 图论

NOIP2024集训Day53 图论

A. [BZOJ4144 ANOOZ2014] Petrol

首先注意到起点和终点都是加油站。

假设中途经过某个非加油站的点 \(u\)，\(u\) 连到 \(v\)，离 \(u\) 最近的加油站是 \(x\)，那么从 \(u\) 到 \(x\) 加油后回到 \(u\)，再到 \(v\) 一定不比直接从 \(u\) 到 \(v\) 差。

因为 \(u\) 一定从某个加油站来，设最后经过的加油站为 \(y\)，\(u\) 点油量为 \(A = b - dis_{y, u}\)，而如果 \(u\) 不可以走到 \(x\) 一定不能走到其他任何加油站自然也到不了终点，如果可以到 \(x\) 加满油也一定可以再从 \(x\) 回来，油量为 \(B = b - dis_{x,u}\)， 因为 \(dis_{y, u} \ge dis_{x, u}\) 所以 \(A \le B\)。

考虑重新构图：\(p_x\) 表示离 \(x\) 最近的加油站，\(dis_x\) 表示 \(x\) 和 \(p_x\) 的距离，可以用多源最短路处理出所有 \(p_x\) 和 \(dis_x\)。

对于原图中边 \((u,v)\) 连边 \((p_u , p_v , dis_u + dis_v + w(u,v))\)。

这就变成了一个图，只选 \(\le b\) 的边问两点连通性，可以离线或者用 Kruskal 重构树做。