樹最大連通分支問題.ppt

樹的最大連通 分支問題,問題描述：,給定一棵樹T，樹中每個頂點u都有一個權(quán)w(u)，權(quán)可以是負(fù)數(shù)?，F(xiàn)在要找到樹T的一個連通子圖使該子圖的權(quán)之和最大。,對于給定的樹T，編程計算樹T的 最大連通分支。,編程任務(wù)：,第1行有1個正整數(shù)n，表示樹T有n個頂點。 樹T的頂點編號為1，n。 第2行有n個整數(shù)，表示n個頂點的權(quán)值。 接下來的n-1行中，每行有表示樹T的一條 邊的2個整數(shù)u,v，表示頂點u與頂點v相連。,數(shù)據(jù)輸入：,由文件input.txt給出輸入數(shù)據(jù)。,結(jié)果輸出：,將計算出的最大連通分支的權(quán)值輸出 到文件output.txt。,input.txt： 5 -1 1 3 1 -1 4 1 1 3 1 2 4 5,輸入文件示例：,1,2,3,4,5,-1,3,1,-1,1,最大連通分支 連通圖 連通圖中各結(jié)點的權(quán)值之和最大,輸出文件示例：,output.txt: 4,1,2,3,4,-1,3,1,1,樹根,root,T1,T2,W0,W0,最大連通分支在子樹或樹中，因此對樹進(jìn)行遍歷，依次求出以每個結(jié)點為樹根的最大連通分支權(quán)值。,Wr=Wr+Wt1,root,T1,T2,W0,W0,算法分析:,問題具有兩個子性質(zhì):,最優(yōu)子結(jié)構(gòu)性質(zhì) 子問題重疊性質(zhì),樹根,root,T1,T2,W0,W0,算法實現(xiàn):,1,2,3,4,5,3,1,-1,1,樹根,-1,對于葉子結(jié)點或兒子個數(shù)為0的 結(jié)點，其最大連通分支權(quán)值為該 結(jié)點的權(quán)值 某一結(jié)點的最大連通權(quán)值0， 則將其值加到它的父親結(jié)點的最 大連通權(quán)值，反之舍棄該值 最后求出根結(jié)點的最大連通權(quán) 值，結(jié)束遍歷 所求最大連通分支權(quán)值即結(jié)點中 的最大連通權(quán)值,數(shù)據(jù)結(jié)構(gòu),struct Cnode long weight; /結(jié)點的權(quán)值 int father; /該結(jié)點的父親結(jié)點 int childnum; /結(jié)點的兒子數(shù) long wMax; /結(jié)點的最大連通分支的權(quán)值 bool visited; /該結(jié)點是否被訪問過 ;,動態(tài)創(chuàng)建數(shù)組表示樹 Cnode *tree=new Cnoden+1; 存儲記錄初始化及數(shù)據(jù)輸入 for (i=1;i(treei.weight);,算法步驟(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.fat