NOIP2024集训Day52 图论

NOIP2024集训Day52 图论

A. [CF1253F] Cheap Robot

先用 Dijkstra 求出每个点离他最近的关键点的距离，设点 \(u\) 的距离为 \(dis_u\)。

设 \(u\) 的容量为 \(x_u\)，那么一定满足 \(c - dis_u \ge x_u \ge dis_u\)，因为它一定要能够从最近的关键点走过来，再走回最近的关键点。

那么如果 \(u\) 到 \(v\) 有一条边边权为 \(w\) 的话，\(dis_v \le x_u - w \le c - dis_u - w\)。

可以得到：\(c\ge dis_u + dis_v + w\)。

现在要找一个最大边权最小的路径，可以发现这个就是最小生成树上的路径。

多次询问倍增。

B. [BZOJ3355 USACO2004JAN] 有序奶牛

对于边 \((u, v)\)，如果删除这条边后 \(u\) 仍然可以到达 \(v\)，那么这条边就可以删掉。

考虑暴力添加每一条边，然后看 \((u, v)\) 是否已经连通。

添加边的顺序是按照终点拓扑从小到大排序，如果相同就按边起点拓扑序从大到小排序。

设置数组 \(f_{u, v}\) 表示 \(v\) 能够到达 \(u\)，每次加边暴力更新，再加上 bitset，时间复杂度 \(\displaystyle\Theta(\frac{nm}{32})\)，可过。