BZOJ2180: 最小直径生成树/图的绝对中心

图的绝u地中心可以在一个点上,也可以在一个边上,可以概括的就认为他在一个含端点的边上。

绝对中心到所有点的最短距离的最大值,肯定有两个点,距离绝对中心距离相同,而且这两个点是一条边的两端。因为如果到这两个点的距离不相等,其中一个还是最短距离最大值,那么我么可以移动绝对中心,使得最短距离最大值变小,就不对了。

这样子我们可以考虑先枚举一下绝对中心所在的边。然后现在某个点距离绝对中心的最短距离,会随着绝对中心在边上的移动而变化。加入绝对中心从一段开始,那么通常情况会先增加,后减小,形如一条折线。因为绝对中心所在的边的两端u和v,开始可能经过u是最短距离,随着绝对中心的移动,经过v是最短距离。相关的图,读者可以自行百度相关博客读图。

一个例图很全的博客。

https://www.cnblogs.com/longshengblog/p/6009395.html

这样子,这个边到每个点都是这样一条折线,由于要取最短距离的最大值,相当于,对于每一个绝对中心的位置,我们取一个所有折线都能取到的最小值,所以我们取,最上面那条折线的最低点。

所以我们按照d[u][w]排序,扫一遍就能求出所有交点的所代表的距离了。

代码中rank维护了下,从某点开始,各点的距离排序。rank中存了编号。然后getrank函数就是一个冒泡排序。floyd函数用来求出各点间的距离,然后solve函数就取图上折线的最低点。

我们发现如果d(x,u)>d(y,u)&&d(x,v)>d(y,v),那么y点无用处,因为代表y的折线在x下方,这也是我们要排序的原因(链接博客里有图)

发表评论