数据结构 2021 小作业7 Hint

[Sakits]

数据结构 2021 小作业7 Hint

1194. 灌水

  建立超级源点，给所有点连代价为打井的边，然后再跑最小生成树就好了。

1195. 方格图

  $dis_{i, j, 0 / 1 / 2}$ 表示到 $(i, j)$ 这个点，已经走的步数模 3 为 0 / 1 / 2 的最小代价。

1196. 架设电话线

  最大值最小化考虑二分，把大于 mid 的边边权设为 1，其他的设为 0 跑最短路，判断是否小于等于 k 即可。

1197. ATM

  求有向图最长路的模板题。

  先求出所有强连通分量进行缩点（因为一个强连通分量中的点是可以两两到达的，所以直接看成一个点就行）。

  接下来我们会得到一个DAG图（有向无环图），进行拓扑排序之后 DP 就可以得到最长路了。

1198. 加油

  暴力做法是把加油站之间的两两最短路给跑出来，然后从小到大往里面加边，并查集维护连通性，离线处理询问。

  这样显然是承受不了的，但其实不需要把两两最短路都给加进去，只需要对于每一条边$(x, y, w)$，设距离 $x$ 最近的加油站 $a$ 到 $x$ 的距离 $d_1$，距离 $y$ 最近的加油站 $b$ 到 $y$ 的距离 $d_2$，把 $(a, b, d_1 + d_2 + w)$ 给加进并查集就好了。

  想要猜到这个结论并不难，但是要想到这个结论的证明并不容易...这里有一个 yyq 提供的证明，如果有同学有其他的证明欢迎来讨论～

  对于从 A 到 B 的一条可能被选择的路径上，所有的点都满足最近加油站要么是 A 要么是 B，并且靠近 A 的点一定满足最近加油站是 A，靠近 B 的点一定满足最近加油站是 B。因为如果不满足这个，也就是存在一个点的最近加油站是 C 的话，走到这个点时先去 C 加油，加油之后再返回这个点一定是更优的选择，而这个就可以分成 A 到 C 和 C 到 B 两条路径了，因此这样的路径不可能被选中。通过这个可以知道这条路径的中间一定有一个分界边，这条分界边的一个端点的最近加油站是 A，另一个端点的最近加油站是 B，所以所有的可能路径都会被上述加边方案包含到。

1199. 序列合并

  设 dist[i][j] 表示到 i 点速度为 j 的最短时间就好了，记一下从哪个点转移的就可以还原路径了。

1200. 山峰

  是两道模版题拼起来：kruskal 重构树 + 主席树。

[LibroWu]

1198是先获得(a,b,weight)然后排序后遍历离线询问然后加入并查集中吗？那这个离任意点最近的加油站怎么找？谢谢ww

[Sakits]

第一个问题是对的～
第二个做法就是新建一个虚点，向所有加油站连长度为 0 的边，然后从虚点出发跑 dij，这样到每个点的最短距离就是最近加油站的距离了