浅析树的划分问题

《浅析树的划分问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、个算法各自的特点。【关键字】问题转化，割，移动，上方【正文】树的划分问题是图论中的一类范围非常广泛的问题，这类题目的大意就是将给定的一棵树划分为若干棵子树，使其能够满足一定的条件或是使得某个特定的函数达到最值。如今，这类问题已被扩展出了各式各样的问题，并在很多领域都有着很广泛的应用。本文所要着重探讨的，是其中一种被称为最大－最小划分的问题。一、问题的提出草莓（NOI2003Day2-2berrytest6~test9）题目大意：给出一片草莓中每个草莓的重量以及它们的连接情况。定义：sum(i)表示第i块草莓田中所有草莓重

3、量的和（1<=i<=k）,x=min{sum(i)

4、1<=i<=k}。你的任务就是要把一块草莓田分割成k块，且分割方案需要满足如下的条件：·每一块中的草莓必然是直接或者间接的和其他草莓相连接的；·这种分割方案所对应的x尽可能的大。最后输出你的分割方案和结果。这是一道提交答案式的题目，其中第6个数据至第9个数据所给的图是一棵树，若不考虑具体的数据情况，我们可以将原问题抽象成如下问题：给定一棵树以及树中每个顶点的一个非负权值，将树划分为k棵子树，定义：sum(i)表示第i棵子树中所有节点权值的和，x=min{sum(i)

5、1

6、<=i<=k}，请求出x的最大值并输出此时的划分方案。简单的说，就是将一棵树划分成k棵子树，使得其中权值和最小的那棵子树最大，我们把它称作最大－最小划分问题。二、算法1：转化问题第1页共7页IOI2004国家集训队论文贝小辉1．转化为新问题初次面对这个问题，或许我们会觉得无从下手，动态规划，贪心等经典算法在这里似乎都不适用，重要的是，我们不知道这个最小值是多少，令我们的思维过程遇到了很大困难。这时，我们不妨先考虑这样一个问题：对于一个确定的下界，最多可将树划分为多少棵子树使得每棵子树的权值和都不小于此下界？2．解决新问题

7、如果可以解决这个问题，我们便可以再通过二分法找到原问题的解。而事实上，新问题的解决只需要一个以贪心思想为基础的扫描算法。扫描算法：按照深度由大至小的顺序扫描整棵树，对于扫描到的每个节点，计算以此节点为根的完全子树的权值和，若权值和大于等于给定下界，则将以这个节点为根的子树划分出来，并将其从原树中删去。直至整棵树所剩部分的权值和小于下界，将剩余部分归入最后划分出去的子树中。最终所得到的即是一种划分数目最多的最优划分。算法正确性的证明比较简单，这里略去了。容易看出，算法的时间复杂度是线性的，已经到达了理论的下界。接下来的任务

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

9、想到：能不能找到一个时间复杂度不依赖于节点权值范围的算法呢？三、算法2：移动算法1．新思路在某一种划分中，如果一条边所连接的两个顶点属于两个不同的子树，那么我们就称在这条边上有一个“割”，我们注意到，每一个割都是对应着一棵子树的，就是这个割下方的所有顶点去掉其他割下方的顶点后所剩下的子树，而只有根节点所在的子树没有与之对应的割。于是，问题就可以转化如何为将k-1个割分配到k-1条边上，使其满足我们期待的最优条件。这样，我们就把问题的重点由对点的划分转化为对割的分配上，换了一种思维方式，我们希望能够因此而找到一种新的解决问

10、题的途径。我们还要介绍一种被称作“移动”的技术，一次移动被定义为将一个割从一条边移到第2页共7页IOI2004国家集训队论文贝小辉另一条与它相邻的边上，并且保证新的边一定是在原来那条边的下一层。也就是说，移动总是由上至下的，这样，我们就有可能通过一个给定的初始划分状态和一系列有限次的移动最后达到某个目标状态。初始状态