poj1155 依赖背包

/*

依赖背包

dp[i][j]表示i结点为根的树选择j个用户时的最大剩余费用

即背包容量是j，价值是最大费用

*/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 3050

struct Edge{int to,nxt,w;}edge[maxn<<];

int n,m,k,head[maxn],tot,num[maxn],dp[maxn][maxn];

void init(){

    memset(head,-,sizeof head);

    tot=;

}

void addedge(int u,int v,int w){

    edge[tot].to=v;edge[tot].w=w;edge[tot].nxt=head[u];

    head[u]=tot++;

}

void dfs(int u,int pre){

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==pre)continue;

        dfs(v,u);

        num[u]+=num[v];

    }

    for(int i=head[u];i!=-;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==pre)continue;

        for(int j=num[u];j>=;j--)

            for(int t=;t<=num[v];t++)

                dp[u][j]=max(dp[u][j],dp[u][j-t]+dp[v][t]-edge[i].w);

    }

//printf("%d %d\n",u,dp[u][1]);

}

int main(){

    int v,w;

    while(cin>>n>>m){

        init();

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)dp[i][j]=-0x3f3f3f3f;

        for(int i=;i<=n-m;i++){//

            cin>>k;

            while(k--){

                cin>>v>>w;

                addedge(i,v,w);

                addedge(v,i,w);

                num[i]=;

            }

        }

        for(int i=n-m+;i<=n;i++)

            num[i]=,cin>>dp[i][];

        dfs(,);

        for(int j=m;j>=;j--)

            if(dp[][j]>=){

                printf("%d\n",j);

                break;

            }

    }

}