BZOJ 4152 [AMPPZ2014]The Captain

发布于 2017-08-16  195 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4152

题意:给定平面上的 n 个点,定义 (x1,y1) 到 (x2,y2) 的费用为 min(|x1-x2|,|y1-y2|),求从 1 号点走到 n 号点的最小费用。


之前在 fks 大爷的模拟题里做到了一个类似这道题的题,虽然秒掉了,还是很有趣的...

首先,可能出现在图里的边只能横/纵坐标排序后相邻的点。

为什么呢?考虑从 u->v,要么直接过去,要么绕一下,u->x->v 过去。

如果绕的这个点在横/纵轴上相比 v 而言,离 x 更近,那么当然绕掉它这样 u->x 和 x->v 都是某维度上相邻的点了。

如果绕的这个点反而更远了,显然不需要绕掉它。

所以证明是显然的,这个性质不止在二维平面有效,在 k 维空间的证明也是类似的。同时,任何具有“最小”性质的图论模型都可以套用它。

很有趣啊。

 


一个非常弱的准退役OIER