依赖背包变形（经典）—

这个题用优化后的依赖背包做难以实现，所以用常规的泛化物品的和来做即可

每个节点的容量定义为这个节点下的叶子结点个数，dp[u][j]用来表示节点u下选取j个物品的最大收益，最后从m-0查询dp[1][i],一旦发现是非负数，i则是答案

需要注意的地方：初始化时将所有的dp[i][0]都赋值为0，一个都不选，代价当然是0

　　　　　　　　dfs遇到u是叶子结点，那么dp[u][1]定义为这个结点的权值，其余状态用-inf来表示不可达

　　　　　　　　其余状态全部赋初始值为-inf，表示目前不可达

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define N 3005

struct Edge{int to,nxt,w;}e[N<<];

int head[N],tot,n,m;

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

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

}

int dp[N][N],a[N],size[N];

void dfs1(int u,int pre){

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

        int v=e[i].to;

        if(v==pre)continue;

        dfs1(v,u);size[u]+=size[v];

    }

}

void dfs2(int u,int pre){

    if(a[u]){dp[u][]=a[u];return;}

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

        int v=e[i].to;

        if(v==pre)continue;

        dfs2(v,u);

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

            for(int k=;k<=size[v];k++)

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

    }

}

int main(){

    memset(head,-,sizeof head);

    cin>>n>>m;

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

        int k,v,w;cin>>k;

        while(k--){

            cin>>v>>w;

            add(i,v,w);add(v,i,w);

        }

    }

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

        cin>>a[i],size[i]=;

    memset(dp,-0x3f,sizeof dp);

    for(int i=;i<=n;i++)dp[i][]=;

    dfs1(,);dfs2(,);

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

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

            cout<<i<<endl;

            break;

        }

}

巴特西

依赖背包变形（经典）——poj1155

最新文章

热门文章