poj1155

题目链接：http://poj.org/problem?id=1155

题意：给你一颗以1为根的树，节点通过条边到其他节点会花费金钱，但是每一条边的花费只会计算一次（如果当前边在之前已经走过，则不会再产生花费），每到一个叶子节点会获得一定的金钱，问在使得最终收益不小于0的情况下，最多可以到达多少个叶子节点。

思路；简单的树形背包 。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF -1e9
using namespace std;
struct{
    int v,w,next;
}edge[6060];
int head[3030];
int cnt;
int dp[3003][3003];//dp[i][j]表示节点i到达j个节点可以获得的最大利益 
int val[3030];
bool vt[3030];
int sum[3030];
void add(int u,int v,int w){
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;

}
int n,m;
void dfs(int k){
    vt[k]=true;
    for(int i=1;i<=m;i++)
    dp[k][i]=INF;//先初始化为无穷小 
    if(k>n-m){
        dp[k][1]=val[k];
    }
    for(int i=head[k];i!=-1;i=edge[i].next){
        if(!vt[edge[i].v]){
            dfs(edge[i].v);
            sum[k]+=sum[edge[i].v]+1;//子树大小 
            for(int j=sum[k];j>=0;j--){
                for(int l=0;l<=j;l++){            
                    dp[k][j]=max(dp[k][j],dp[k][j-l]+dp[edge[i].v][l]+edge[i].w);
                }
            }
        }
    }
}
int main(){
    int k,v,w;
    scanf("%d%d",&n,&m);
    cnt=0;
    fill(head,head+3003,-1);
    for(int i=1;i<=n-m;i++){
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            scanf("%d%d",&v,&w);
            add(i,v,-w);
            add(v,i,-w);
        }
    }
    for(int i=n-m+1;i<=n;i++){
        scanf("%d",&val[i]);
    }
    dfs(1);
    bool lg=true;
    for(int i=m;i>=1&&lg;i--){
        if(dp[1][i]>=0){
            printf("%d
",i);
            lg=false;
        }
    }
    if(lg)
    printf("0
");
    return 0;
}