NOIP 2018 集训 Day 3

图论

图的存储

• 邻接矩阵（$\text{O}(n^{2})$）
• 邻接表（时间复杂度$\text{O}(n+m)$，空间复杂度$\text{O}(n^{2})$）
• 邻接链表（$\text{O}(n+m)$）

图的遍历

$\text{bfs}$

计算无权图或树上最短路、求连通块比较实用。

输出路径可以用$\text{dis}$乱搞，也可以在松弛的时候记录路径上的上一个点（也可以叫做最短路径树上的父节点）。

输出字典序最小的路径，可以在反图上进行搜索，再根据字典序倒推路径的上一个点。

$\text{printf}$输出技巧 printf("%5d",x);右对齐占$5$格，printf("%-5d",x);左对齐占$5$格。

障碍路线

状态包含位置和朝向。

巧妙地设计转移坐标数组turnx[]={0,1,0,-1};turny[]={1,0,-1,0};，使向右转恰好是$+1 \pmod{4}$，左转恰好是$-1 \pmod{4}$。

为了使用$\text{bfs}$，要一次性将所有下一个转弯的位置加入队列中，搜到终点直接返回即可。

防止重复的要点：强制至少走一步，不允许原地转弯。

最优贸易

强连通分量缩点+$\sout{\text{DAG}}$上$\sout{\text{dp}}$

纯$\text{bfs}$！厉害吧。

注意到价格很小，考虑到按价格拆点。

先去除所有不能到达$n$的点，可以在反图上$\text{bfs}$或$\text{dfs}$。

$\text{f}[i][j]$表示到达$i$时所经过的点的最低价为$j$能否实现。从起点开始进行$\text{bfs}$，对于遍历到的每个可能状态$\text{f}[i][j]$，用$\text{price}[i]-j$更新答案。如果发现了一个新的可能状态，就把它入队。

关押罪犯

对答案二分，用$\text{bfs}$或$\text{dfs}$染色，自动过滤掉边权不大于答案的边。$\text{O}((n+m)\log c)$。

$\text{DAG}$

车站分级

直接拓扑排序边会过多，要添加虚拟的中间点，两个级别的车站连边时，上一级别的车站统一向虚拟点连边，再由虚拟点连向下一级别的车站。

这么做的原因是，题目给出的是$\forall (x,y) \in A \times B,x<y$这样的关系。

回忆我们解数学题时处理这样的条件的过程：$\forall x_{1}\in [a,b],\forall x_{2}\in [c,d],f(x_1)>g(x_2)$。我们可以把它转化为$f(x)$在$[a,b]$内的最小值大于$g(x)$在$[c,d]$内的最大值。

进行知识迁移，我们把信息转化为$\min(A)>\max(B)$。我们不妨设虚拟点的分级为$\frac{\min(A)+\max(B)}{2}$，则信息转化为，上一级别的所有车站的分级大于虚拟点的分级，下一级别所有车站的分级小于虚拟点的分级，这样这道题的难点就解决了。

最短路

$\text{SPFA}$优化

被称为$\text{SLF(Small label first)}$策略。若当前入队的顶点的$\text{dis}$比队头的$\text{dis}$小，就将这个点从队头插入；否则插入队尾。在随机图上表现得不错，但是在恶意构造出的数据上会表现出$\text{O}(2^n)$的复杂度~~，死得更惨~~。

道路重建

考虑把已经有公路连接的点缩成同一个点，重新建图跑最短路即可。

其实不需要重新建图，把完好的公路的权值改为$0$即可。

INGRED

最暴力的方法是先用$\text{Floyd}$计算出任意两点间的最短路，再枚举两个人访问的特殊点，再枚举访问的顺序，更新答案即可。

比较好的方法是利用特殊点比较少的性质，从每个起点开始跑最短路。把每一个点的状态信息扩充，即把已经访问的特殊点记入点本身，或者说是“拆点”，把每一个点拆成$2^s$个，点$(x,\text{status})$表示到点$x$且状态为$\text{status}$的最短路。最后枚举两个人分别走过的特殊点，直接计算答案即可。这样之所以能带来速度提升，是因为它把前面暴力方法中连续枚举（即复杂度相乘）的访问顺序变成了分开枚举（复杂度相加）。

计算特殊的最短路时，拆点时很重要的技巧。如飞行路线。