隨筆-72 評論-126 文章-0 trackbacks-0

#include "stdio.h"

struct Tree{
    int father;
    int child;
    int brother;
    int TakeParty;
    int Not;
    int Max() {
        return TakeParty > Not ? TakeParty : Not;
    }
    void init() {
        father = child = brother = Not = 0;
    }
}tree[6001];

void dfs(int idx ) {
    int child;
    child = tree[idx].child;
    while(child) {
        dfs(child);
        tree[idx].TakeParty += tree[child].Not;
        tree[idx].Not += tree[child].Max();
        child = tree[child].brother;
    }
}

int main() {
    int n,i,a,b;
    while(scanf("%d",&n) == 1) {
        for(i =1 ; i <= n ; i ++) {
            scanf("%d",&tree[i].TakeParty);
            tree[i].init();
        }
        while(scanf("%d%d",&a,&b),a+b) {
            tree[a].father = b;
            tree[a].brother = tree[b].child;
            tree[b].child = a;
        }
        for(i = 1 ; i <= n ; i ++) {
            if(!tree[i].father) {
                dfs(i);
                printf("%d\n",tree[i].Max());
                break;
            }
        }
    }
    return 0;
}

posted on 2009-05-11 20:39 shǎ崽閱讀(6207) 評論(4) 編輯收藏引用

評論:

# re: 樹形DP 2009-05-12 17:16 | zjfc3

左兒子右兄弟法？？不錯回復更多評論

# re: 樹形DP 2010-08-08 11:36 | TT

LZ有沒hdu 1561的代碼學習下回復更多評論

# re: 樹形DP 2013-04-07 21:29 | 隨心小亞

@TT
1561 的代碼我有，但是不知道如何判斷-1的情況：
var
n,m,i:longint;
fa,w:array [1..200] of longint;
f:array [0..200,0..200] of longint;
procedure dfs(h,s:longint);
var
i,j:longint;
begin
if s<=0 then exit;
for i:=1 to n do
if fa[i]=h then begin
for j:=0 to s-1{cost[child]} do f[i,j]:=f[h,j];
dfs(i,s-1{cost[child]});
for j:=1{cost[child]} to s do
if f[h,j]<f[i,j-1]+w[i] then
f[h,j]:=f[i,j-1]+w[i];
end;
end;
begin
repeat
readln(n,m);
if not ((n=0)and(m=0)) then begin
for i:=1 to n do readln(fa[i],w[i]);
dfs(0,m-0);
writeln(f[0,m-0]);
end;
until (n=0)and(m=0);
end. 回復更多評論

刷新評論列表