樹(shù)最大連通分支問(wèn)題.ppt

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