【题解】洛谷P2149 [SDOI2009]Elaxia的路线

题目

洛谷P2149 Elaxia的路线

题解

要求最短路的公共路径,首先需要分别找出两个点对的最短路径。注意:最短路径不一定是一条 链,由于可能存在多条长度相同的最短路径,这些路径构成了一张图。考虑到起点S到终点T的最短路径和T到S的相同,所以就简化,只考虑S到T的最短路径(有向),于是,此时的最短路径就构成了一张DAG(有向无环图)。

找出最短路径的(其中一种)方法:先求出最短路径,然后用dijkstra算法求出S点到每个点的最短距离ds[](前两个步骤同时进行),同理求出T点到每个点的最短距离dt[]。枚举每一条边,假设边的两个端点是x,y(此边为有向边x->y),如果ds[x]+边权+dt[y]=最短路径长度,则该边位于S->T的最短路上;如果dt[x]+边权+ds[y]=最短路径长度,则该边位于T->S的最短路上。

拓扑排序(必备知识):在DAG上,找到入度为0的点排在序列的最前面,然后删掉这个点和其连接的边,找到下一个入度为0的点,重复上述操作。这种排序方式可以保证每个点排在它的前驱节点后面,排在它的后继节点前面。沿着DAG的拓扑序dp可以保证无后效性。

dp方式(结合下图及图下方文字理解):可以沿着其中一个点对(S1,T1)的最短路径DAG进行统计,但是可能有问题,就是统计到的公共路径不一定是另一个点对(S2,T2)的同一条最短路上的。易证:最短路DAG中的任意一条路径都是有向的链。同时,最长公共路径也必定是一条链(可用反证法证明:若是分开的两条链,显然这两条链都位于两个点对的最短路DAG上,且包含这两条链的两条最短路径在两条链之间的路径不同,这两段不同的路径,若长度相同,则都为最短路,那么两条链之间的路径也算公共最短路,若长度不同,则长的那一条不是最短路,可以局部优化成短的那一条路径)。所以,在两个最短路DAG的公共路径上,两条最短路的有向链要么方向相同(如下图:公共路径:1-4-5),要么方向相反(如下图:公共路径“1-2-3或5-6-7”)。所以,在dp时,需要同时记录当前的同向链长度和反向链长度。

配图解释:S1=1,T1=7,S2=3,T2=5,红色箭头表示S1->T1的最短路DAG,蓝色箭头表示S2->T2的最短路DAG。 在3->7->6->5这条蓝色最短路上,3->7,5->6->7分别属于两条红色最短路。

存边技巧:将无向边拆成两条有向边时,将每组边的下标定为0/1、2/3、4/5。这样可以通过^1找到组内另一条边。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月22日 上午8:57

【小白解析】
此问题主要难点在于拓扑排序和动态规划的结合运用。其中dijkstra()算法已在先前章节中多次运用,此不再赘述。
先用较简明的语言阐述拓扑排序:所谓有向图中一个点的“入度”,指的是通往该点的路劲总数。若图中一点入度为0,说明没有线路能到达该点,只有可能是从该点出发走上其他线路。故这些入度为0的点必然是当前状态下的“起点”。搜寻一个起点,追溯其所有路径以及通向的“终点”,每考察完一个终点,就将通向该终点的路径消除(具体体现为将该终点的入度减1,见第75行的in[y]–)。操作完当前的终点后,若终点的入度也变成0,说明它成为了原起点所通向的下一个“起点”,故将其推入队列中。
*此处使用队列而非栈,大概是为了保证先加入的起点先被考察,符合排序的需要。具体原因希望各位大神做进一步阐述。
需要注意的是,in[i]的初始化是在get_path1()方法中实现的(见第46行),而get_path2()并未参与。说明所谓“入度”是根据S1->T1的角度建立的,即排序中默认的“方向”是S1->T1的各线路方向。

本题解的另一个要点在于对线路方向的表示、压缩与解压。在存储每一条线路时,程序都预存了两个方向:92行的代码将x->y与y->x的路径分别存储在下标相邻的两个e[i]成分中(2/3,4/5,6/7,……不从0/1开始的原因是0作为下标,通常不满足循环要求(见第28行等))。这一要点的运用集中体现在71-73行中:先考察S1->T1最短路径中,是否包含线路i(x->y)。若包含,并且S2->T2中同样包含该线路,则f1[y]与f1[x]+e[i].w做对比,看新生成的以y为终点的最长同向公共线段是否需要更新;若包含但S2->T2中该线路的方向相反(即包含线路i^1(y->x)。异或操作i^1的作用是保留i在二进制表示下除最后一位外所有位数,将其最后一位取反。具体体现成:若i位奇数,结果为i-1;若i为偶数,结果为i+1。这与线路不同方向的储存一致。),则考察最长反向公共线段是否需要更新。最后比对两种线路与现有答案的大小,取最大值即为答案。
*<bits/stdc++.h>头文件,永远的神。
**顺便祝E和W同学终成眷属好了。