算法合集之《浅析树的划分问题》.pdf

IOI2004国家集训队论文贝小辉

浅析树的划分问题

东北育才学校贝小辉

【摘要】
树的最大－最小划分问题可以表述为如下形式：给定一棵n个节点的树以及每个节点
的一个非负权值，要求将这棵树划分为k棵子树，使得子树中所有节点权值和的最小值最大。
将原问题转化为对于给定下界，划分最多子树的问题，并通过对新问题的解决结合二分法来
解决原问题是可行的，但是算法的总复杂度要依赖于节点权值的范围。本文接下来介绍了一
个时间复杂度不依赖于节点权值范围的算法，随后通过对算法的描述、正确性的证明来进一
步探讨算法的特点，并介绍了算法的一些扩展，最后总结了两个算法各自的特点。

【关键字】
问题转化，割，移动，上方

【正文】
树的划分问题是图论中的一类范围非常广泛的问题，这类题目的大意就是将给定的一
棵树划分为若干棵子树，使其能够满足一定的条件或是使得某个特定的函数达到最值。如今，
这类问题已被扩展出了各式各样的问题，并在很多领域都有着很广泛的应用。本文所要着重
探讨的，是其中一种被称为最大－最小划分的问题。

一、问题的提出

草莓（NOI2003Day2-2berrytest6~test9）
题目大意：
给出一片草莓中每个草莓的重量以及它们的连接情况。定义：sum(i)表示第i块草莓田
中所有草莓重量的和（1<=i<=k）,x=min{sum(i)|1<=i<=k}。你的任务就是要把一块草
莓田分割成k块，且分割方案需要满足如下的条件：
·每一块中的草莓必然是直接或者间接的和其他草莓相连接的；
·这种分割方案所对应的x尽可能的大。
最后输出你的分割方案和结果。

这是一道提交答案式的题目，其中第6个数据至第9个数据所给的图是一棵树，若不
考虑具体的数据情况，我们可以将原问题抽象成如下问题：给定一棵树以及树中每个顶点的
一个非负权值，将树划分为k棵子树，定义：sum(i)表示第i棵子树中所有节点权值的和，x
=min{sum(i)|1<=i<=k}，请求出x的最大值并输出此时的划分方案。
简单的说，就是将一棵树划分成k棵子树，使得其中权值和最小的那棵子树最大，我
们把它称作最大－最小划分问题。

二、算法1：转化问题

IOI2004国家集训队论文贝小辉

1．转化为新问题
初次面对这个问题，或许我们会觉得无从下手，动态规划，贪心等经典算法在这里似
乎都不适用，重要的是，我们不知道这个最小值是多少，令我们的思维过程遇到了很大困难。
这时，我们不妨先考虑这样一个问题：
对于一个确定的下界，最多可将树划分为多少棵子树使得每棵子树的权值和都不小于
此下界？

2．解决新问题
如果可以解决这个问题，我们便可以再通过二分法找到原问题的解。而事实上，新问
题的解决只需要一个以贪心思想为基础的扫描算法。

扫描算法：

按照深度由大至小的顺序扫描整棵树，对于扫描到的每
个节点，计算以此节点为根的完全子树的权值和，若权值和
大于等于给定下界，则将以这个节点为根的子树划分出来，
并将其从原树中删去。直至整棵树所剩部分的权值和小于下
界，将剩余部分归入最后划分出去的子树中。最终所得到的
即是一种划分数目最多的最优划分。

算法正确性的证明比较简单，这里略去了。容易看出，算法的时间复杂度是线性的，
已经到达了理论的下界。接下来的任务就很简单了：我们可以通过二分法来找到最大的下界
x使得划分的最大子树数目不小于k，x既为原问题的解。
3．小结
我们终于找到了一种解决问题的途径，但问题是否已经被完美的解决了呢？当我们分
析这个算法总的时间复杂度是时候，我们发现它是依赖于节点权值的范围的。更加确切的说，
如果每个节点权值的上界是c，那么算法的时间复杂度就是O(nlog(nc))。虽然在大多数情
况下，程序的实际运行效率是比较好的，在解决berry那个问题时，所有数据也都能很快出
解，但是当节点的权值范围很大或权值是实数时，算法便不是那么令人满意了。于是，我们
自然而然地想到：能不能找到一个时间复杂度不依赖于节点权值范围的算法呢？

三、算法2：移动算法

1．新思路
在某一种划分中，如果一条边所连接的两个顶点属于两个不同的子树，那么我们就称
在这条边上有一个“割”，我们注意到，每一个割都是对应着一棵子树的，就是这个割下方
的所有顶点去掉其他割下方的顶点后所剩下的子树，而只有根节点所在的子树没有与之对应
的割。于是，问题就可以转化如何为将k-1个割分配到k-1条边上，使其满足我们期待的最
优条件。这样，我们就把问题的重点由对点的划分转化为对割的分配上，换了一种思维方式，
我们希望能够因此而找到一种新的解决问题的途径。
我们还要介绍一种被称作“移动”的技术，一次移动被定义为将一个割从一条边移到

IOI2004国家集训队论文