2010年1月30日星期六.sgu143 樹(shù)狀動(dòng)態(tài)規(guī)劃
sgu143:Tree DP
題目給出n(1 <= n <= 16 000)個(gè)點(diǎn)，n-1條邊，每個(gè)點(diǎn)都有一個(gè)權(quán)值，求最大連通子圖。
由于題目給出的圖邊比點(diǎn)少一個(gè)，隨意也就是一棵樹(shù)，所以題目所求的也就變成了最大連通子樹(shù)。
可以深搜，每個(gè)點(diǎn)的的最大連通子樹(shù)的權(quán)等于這個(gè)點(diǎn)的權(quán)值+它所有未訪問(wèn)鄰接點(diǎn)的正權(quán)和。
1 const int N = 16100;
2 int n,val[N],vis[N],res;
3 vector<int> g[N];
4 //http://m.shnenglu.com/schindlerlee
5 int dfs(int u)
6 {
7 vis[u] = true;
8 int sz = g[u].size(),i, cur = val[u],tmp;
9 for (i = 0;i < sz;i++) {
10 if (!vis[g[u][i]] && (tmp = dfs(g[u][i])) && tmp > 0) {
11 cur += tmp;
12 }
13 }
14 if(cur > res) { res = cur; }
15 return cur;
16 }
res 初值為-inf,最后res就是結(jié)果。