poj1155 TELE （树上分组背包）

题目链接：https://vjudge.net/problem/POJ-1155

题意：给定一颗以1为根的边权树，有n个结点，其中m个叶子结点，每个叶子结点有一个价值。要求从m个叶子结点中选最多的结点，费用是从根节点到叶子结点的边权和，价值是所有选中的叶子结点价值和。

思路：

　　树上分组背包。用dp[u][j]表示对于结点u的子树，选j个叶子结点的最大利润，即价值-花费。因为对u的每个子结点v1,v2,v3，在v1的子树中最多选择一种方案，不可能重叠选择，所以是分组背包。先处理出num[u]，表示结点u的子树中叶子结点的个数。

　　那么对于叶子结点u：dp[u][j]=a[u]（a[u]是叶子结点u的价值）

　　　　对于非叶子结点u：dp[u][j]=max(dp[u][j] , dp[u][j-k]+dp[v][k]-len)，其中j是最大容量，k是枚举的容量。

　　dp数组初始化为负无穷，因为一条利润为负数的方案在后面也可以和另一条利润正的方案合并，最终利润仍为正。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

const int ninf=0xcfcfcfcf;

int n,m,head[maxn],a[maxn],cnt,dp[maxn][maxn],num[maxn];

struct node{

    int v,w,nex;

}edge[maxn];

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

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void dfs(int u){

    if(!head[u]){

        dp[u][]=a[u];

        num[u]=;

        return;

    }

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        dfs(v);

        num[u]+=num[v];

    }

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

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

            for(int k=;k<=min(j,num[v]);++k)

                if(dp[u][j-k]!=ninf&&dp[v][k]!=ninf)

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

    }

}

int main(){

    scanf("%d%d",&n,&m);

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

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

            dp[i][j]=ninf;

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

        int k,t1,t2;

        scanf("%d",&k);

        for(int j=;j<=k;++j){

            scanf("%d%d",&t1,&t2);

            adde(i,t1,t2);

        }

    }

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

        scanf("%d",&a[i]);

    dfs();

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

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

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

            break;

        }

    return ;

}

巴特西

poj1155 TELE （树上分组背包）

最新文章

热门文章