Dec 18, 2016 修文: 此篇算法是错的, 底下性质二的证明不正确.
认真回一篇好了.
这题只需要一次 BFS 计算每个位置下列两个值即可. 令 d(v) 为起点至该点图上的距离.
当说到 "在某位置停留" 时指的是在该位置重复获利 (即使用了 self-loop).
一. 不在任何位置停留下起点到该点 v 走过 d(v) 步最佳获利
二. 从起点到该点经过 N 天 (N 为题目所给天数) 最佳获利
值一可简单 DP 完成, 或是一并在计算值 (2) 之 BFS 时计算.
值二不难看出等价于
二'. 从起点不在任何位置停留, 经过 d(v) 步抵达该点 v 后停留至 N 天之最佳获利
(我们只需证明以下性质: 最佳获利途径必为起点 d(v) 步直达终点后停留原地获利.
性质一. 最佳路径上终点必有最大获利.
证明. 假设不然, 则路径上有一位置 w 获利为最大(必然大过终点).
则由起点出发延最佳路径抵达 w 后停留至 N 天必获利更多, 矛盾. ▓
性质二. 最佳路径必为图上从起点至终点最短路径, 不经停留, 留在终点获利.
证明. 由性质一可知越早抵达终点越佳; 若最佳路径不为最短路径, 则使用最短路径抵达
终点后停留必可获利更多, 矛盾.
Dec 18, 2016 修文: 此证明忽略了最短路径上获利可能很低, 因此是错误的.
)
值二'利用值一常数时间即可计算.
此图每个位置只有最多八个邻居, 所有位置值一可在线性时间计算完成.
(事实上最短路径方向的关系, 只有最多三个邻居有影响.)
而执行 BFS N 步后 (若所要求天数少 BFS 深度可提早终止), 将值二最大的位置与值输
出即可. 连路径都需要的话在 DP 时记录前一个位置即可.
整个算法可在线性时间完成.
不难看出这个算法可推广到任意图, 而执行时间仍然为线性.
(当然, 这时图的边数也会被算在内.)