题目
分析
首先把最短路径树画出来(由题意最短路径唯一,所以是树):
其中1是根。我们将树记作T,i的子树记作B。图中,B是绿色点,T-B是红色点。
而1~i最短路上的最后一条边(也就是不能走的边)即i的父亲边。将这条边去掉以后,1~i的最短路长什么样呢?
可以发现,一定是这样的:
即,先从1沿着树边走到T-B中的某个点u,然后再沿着某条非树边走到B中的某个点v,然后再沿着树边走到i。
为什么这样是对的呢?假设这条最短路上最后一个T-B中的点是u,那么1~u[……]
渺渺苍天,星光烁烁,美丽家园球外乡
算法就是:枚举凸包的最左下点B,然后将所有合法的点按相对于B的极角序排序,这样凸包上的点一定是顺序选的。然后记忆化搜索:设状态f(B,p2,p3)代表:最左下点为B,凸包上选的最后一个点为p2,正在测试选不选p3.那么有两种转移:①不选p3,将p3改为p2->p3这条射线沿逆时针旋转卡到的第一个点。②选p3,将p2改为p3,p3改为以p3为起点,方向为p2->p3的射线沿逆时针旋转卡到的第一个点。
这个过程很像是Graham和卷包裹法的某种[……]