《树最大连通分支问题》由会员分享，可在线阅读，更多相关《树最大连通分支问题（12页珍藏版）》请在金锄头文库上搜索。
1、树的最大连通树的最大连通分支问题分支问题问题描述：问题描述：给定一棵树给定一棵树T T，树中每个顶点，树中每个顶点u u都有都有一个权一个权w(u)w(u)，权可以是负数。现在要找，权可以是负数。现在要找到树到树T T的一个连通子图使该子图的权之和的一个连通子图使该子图的权之和最大。最大。对于给定的树对于给定的树T T，编程计算树，编程计算树T T的的最大连通分支。最大连通分支。编程任务：编程任务：第第1 1行有行有1 1个正整数个正整数n n，表示树，表示树T T有有n n个顶点。个顶点。 树树T T的顶点编号为的顶点编号为1 1，n n。第第2 2行有行有n n个整数，表示个整数，表示n
2、n个顶点的权值。个顶点的权值。接下来的接下来的n-1n-1行中，每行有表示树行中，每行有表示树T T的一条的一条 边的边的2 2个整数个整数u,vu,v，表示顶点，表示顶点u u与顶点与顶点v v相连。相连。数据输入：数据输入：由文件由文件input.txtinput.txt给出输入数据。给出输入数据。结果输出：结果输出：将计算出的最大连通分支的权值输将计算出的最大连通分支的权值输出出 到文件到文件output.txtoutput.txt。input.txtinput.txt： 5 5-1-11 13 31 1-1-1 4 41 1 1 13 3 1 2 1 2 4 5 4 5输入文件示例：输
3、入文件示例：1 12 23 34 45 5- -1 13 31 1- -1 11 1最大连通分支最大连通分支连通图连通图连通图中各结点的权值之和最大连通图中各结点的权值之和最大输出文件示例：输出文件示例：output.txt:output.txt: 4 41 12 23 34 4- -1 13 31 11 1树根树根rootrootT1T1T2T2W W000 最大连通分支在子树或树中，因此对树最大连通分支在子树或树中，因此对树进行遍历，依次求出以每个结点为树根的最进行遍历，依次求出以每个结点为树根的最大连通分支权值。大连通分支权值。W Wr=r=W Wr+r+W Wt1t1rootrootT
4、1T1T2T2W W000算法分析算法分析:问题具有两个子性质问题具有两个子性质:最优子结构性质最优子结构性质子问题重叠性质子问题重叠性质树根树根rootrootT1T1T2T2W W000算法实现算法实现:1 12 23 34 45 53 31 1- -1 11 1树根树根- -1 1对于叶子结点或儿子个数为对于叶子结点或儿子个数为0 0的的 结点，其最大连通分支权值为该结点，其最大连通分支权值为该 结点的权值结点的权值某一结点的最大连通权值某一结点的最大连通权值0 0， 则将其值加到它的父亲结点的最则将其值加到它的父亲结点的最 大连通权值，反之舍弃该值大连通权值，反之舍弃该值最后求出根结点
5、的最大连通权最后求出根结点的最大连通权 值，结束遍历值，结束遍历所求最大连通分支权值即结点所求最大连通分支权值即结点中中 的最大连通权值的最大连通权值数据结构数据结构struct Cnodelong weight; /结点的权值结点的权值int father; /该结点的父亲结点该结点的父亲结点int childnum; /结点的儿子数结点的儿子数long wMax; /结点的最大连通分支的权值结点的最大连通分支的权值bool visited; /该结点是否被访问过该结点是否被访问过;weightfatherchildnumwMaxvisited动态创建数组表示树动态创建数组表示树Cnode
6、*tree=new Cnoden+1;存储记录初始化及数据输入存储记录初始化及数据输入 for (i=1;i(treei.weight);算法步骤算法步骤(1)(1)for (i=1;iuv; treev.father=u; treeu.childnum+; treei.wMax=treei.weight;确定树根确定树根 for (i=1;i0 for (i=1;i0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; 求出最大的连通分支权值求出最大的连通分支权值算法步骤算法步骤(2)(2)最大时间复杂性：最大时间复杂性：O(n2)
