专栏文章

9.7 最短路

MMourning_Angemilia
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minza9j6
此快照首次捕获于
2025/12/02 10:47
3 个月前
此快照最后确认于
2025/12/02 10:47
3 个月前
查看原文

T1:

非常经典的一道分层图题。这道题的核心是最短路，但与板子不同的是，这道题有kk次免费机会可以用
如果用简单地贪心思想，我们最短路径上把花费最多到第kk多的边用完kk次免费就肯定最优
但是，如果更改边权，做法就会非常麻烦。并且kk次机会不保证能够用完。既然改原边很麻烦，那么我们就可以想着去建新边。既然有那么多建的边，就肯定会是达到建图的程度。于是分层图就来了
既然我们可以使用kk次免费机会，我们不妨额外建kk张图。因为一张图nn个点，我们在建新图时，对应点的编号就为i+n∗ji+n*j，其中ii为点的原图编号，jj为第jj层图（1≤j≤k1 \leq j \leq k）
点确定了，还有问题就是如何建边？由于新图约等于原图，那么在同一张图中的点之间连边与原图相同。但如果是相邻两层图连边，边权就不一样了。因为第j−1j-1层图转移到第jj层时，就说明使用了一次免费机会，那么两点之间边权就为00（边权更改与题目相关，就像P4822 [BJWC2012] 冻结所述，边权要变为原来的一半）

T2:

核心在于奇偶最短路。询问从一节点出发是否走xx步可以到达指定节点。那么我们发现，如果先走一步最短路，那么多余的部分我们是可以凑出来的：向上个节点走一步，再走回来
但是这很明显有限制。由于多余步数我们在凑的时候，凑一次就要消耗两步。举个例子，有一条链，节点为1、2、31、2、3。11链接22，22链接33，那么最短步数肯定是为22步。如果需要恰好33步从11号节点到33号节点，肯定是为无解
那么，我们合理推导，不难发现解决做法。维护dis1dis1表示到节点xx的奇数步，dis2dis2则表示偶数步。按dijkstradijkstra模板来，那么松弛就要改为如下代码:
CPP
  if(dis2[nxt]>dis1[cur]+1)
  {
    di[nxt][2]=true;
    dis2[nxt]=dis1[cur]+1;
    q.push(nxt);
  }
  if(dis1[nxt]>dis2[cur]+1)
  {
    di[nxt][1]=true;
    dis1[nxt]=dis2[cur]+1;
    q.push(nxt);
  }
由于空间给的比较小，排序起点编号优化一下空间即可

T3

题意：连接SS中的两个点，求最短路的最大值
我们可以选取SS中的任意两点u,vu,v，定义dis1kdis1_k为11到kk的最短路，dis2kdis2_k为kk到nn的最短路
那么在边连接之后u,vu,v距离为11，则我们要让dis1u+dis2v+1dis1_u+dis2_v+1最大，于是就有了一个O(k2+mlogn)O(k^2+mlogn)的算法。在本题数据下，这个时间复杂度肯定是过不了的。那么我们有没有优化呢？有！
dis1u+1+dis2v≤dis1v+dis2v≤dis1ndis1_u+1+dis2_v\leq dis1_v+dis2_v \leq dis1_n，并且由dis1v+dis2vdis1_v+dis2_v已知则可以推出最短路从dis1v+dis2vdis1_v+dis2_v减少了dis1v−dis1u−1dis1_v−dis1_u−1，此时我们让dis1v−dis1udis1_v−dis1_u最小则最短路为最大值
我们只要跑两遍bfsbfs求dis1,dis2dis1,dis2，按dis1kdis1_k的值从小到大排序，输出最大的最短路即可

T4

这是个差分约束的题，至于差分约束是个什么玩意，可看下方解释：
差分约束系统是一种特殊的nn元一次不等式组，它可以包含nn个变量x1,x2......xnx_1,x_2......x_n以及mm个约束条件，每个约束条件是由两个其中的变量做差构成的，形如xi−xj≤ckx_i-x_j\leq c_k
我们需要解决的问题就是求一组解x1=a1,x2=a2...xn=anx_1=a_1,x_2=a_2...x_n=a_n，让所有约束条件可以得到满足，否则就是为无解
那么对于这道题，它的题面并没有直接告诉我们是差分约束，我们如何判断？
我们不难发现，由于差分约束核心在于不等式。那么如果出现不超过，不少于这一类字眼，再加上有时题目无解，就很有可能是差分约束题
既然方法知道了，怎么从题目中得到不等式却是个问题。如果我们假设有数组aa，其中aia_i表示第ii小时需要的最少人数
如果我们雇佣了一个人，那么这个人工作的时间是可以工作2−82-8小时。那么如果有一个人需要在第ii时刻工作，他最早就是在第i−8i-8小时的时候就开始工作了。由于每一个时间段都会是一批一批人，我们用sumsum数组预处理前缀和，那么就可以得到不等式：
ai≤sumi−sumi−8a_i\leq sum_i-sum_{i-8}
由于一天2424小时，有些人可能在前一天就会值班了，所以这是个环形问题。于是乎，这个题目又满足不等式sumi−1≤sisum_{i-1} \leq s_i。最少需要的人数量便是为sum24sum_{24}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...