ZOJ 3820 ACM 牡丹江 Building Fire Stations

SXBK的一个题(对我现在的水平来说)

其实是这样,对于一棵树,在上面建1个消防站,最优位置在直径中心,建立两个消防站呢?其实可以把整个大树分成两个小树,在每个小树自己的直径的中心建立消防站就搞定了,在分树的时候,如果发生分歧(如果直径有奇数个点,就会出现这种分歧情况,如果有偶数个节点,中央节点有两个,直接从两个节点的中央裂开就行,不会产生分歧),这时候我把中央节点上连接的那些节点中除了直径上的两点之外的那些节点都叫做中立节点,我们只要进行两次讨论,一次把这些中立节点分入左半树,求出这种分法中左右半树的直径,然后把左右直径的最大值当成接下来判定哪个方法更好的基准(因为我们要的是最长距离的最小值),然后再把这些中立节点分入右半树,搞出相应的解,接下来我们比较刚才保存下来的基准,哪个小要哪种方案,这样我们就把最终的解搞出来了。

我觉得其实这种思路还可以推广,如果建立3个,4个乃至n个,我们也可以切割树求直径来搞。

然后切树是,我们可以通过把某个点“屏蔽”,来实现不会让dfs进入另一半子树的目的。

其实这个题还可以通过枚举大直径上的两点求出最优解来解决,思路也是比较清晰的。

 

Leave a Reply

Scroll to top