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})\)，可过。
C. [NOI2009] 变换序列
每个位置上只有 \(2\) 种情况，很明显的二分图匹配。
因为要求字典序最小，我们考虑匈牙利算法的运行方式，是保证当前匹配的点最优，所以连边时将字典序小的点尽可能后连，保证第一个邻接表第一个选出来的点是字典序最小的，最后跑匈牙利时从 \(n - 1\) 到 \(0\) 即可。
D. [CF843D] Dynamic Shortest Path
《真·动态最短路》
但是因为每次只加 \(1\)，所以可以每一次修改操作的时候使用距离分层的 bfs，在 \(\Theta(n)\) 的时间内解决修改。
这里要用到一个小技巧：
把每条边 \((u, v)\) 的边权表示为 \(dis_u + w(u,v) - dis_v\)，这样边权实际上变成了这条边离作为最短路的一份子还差了多少。
然后在用这个边权的新图里面更新 \(1\) 到每个点的最短路，再用原来的 \(dis\) 加上这个值，就是当前的最短路了。
实际上是把绝对数值转化为了离最优解的距离。
E. [ARC076F] Exhausted
如果有一个限制（如必须 \(\le x\)），直接对其排序，从左往右扫即可。
现在有两个限制，那么我们就可以把一些左边放不下的放到右边去，当然是右边 \(\ge x\) 的限制 \(x\) 越小越好，用小根堆即可解决。
Hall定理那个做法不想写了