题解 P1273 【有线电视网】

tth37 · 2019-04-25 17:39:16 · 题解

背包类树形dp。本题需要运用分组背包模型。

首先定义状态：f[u][i]表示以u为根的子树上，选择i个用户时的最大利润。由于电视公司可能亏本，因此f数组应赋极小初值。

可以将选择的用户个数看作背包的容量维度，将获得的利润看作背包的价值维度。可以设计出如下的状态转移：

其中，v为u的子节点，w为这条边的权值。在u每个子节点上有许多“物品”，“物品”总数即为以v为根的子树上用户的个数；每个“物品”所具有的价值即为其最大利润，即f[v][j]。同时不应忽略边权对利润带来的影响。

注意细节处理。代码如下：

#include<bits/stdc++.h>
using namespace std;

struct Edge{
    int v,w,nxt;
}mem[3005*2];
int head[3005],cnt;
int size[3005];

inline void AddEdge(int u,int v,int w){
    mem[++cnt].v=v;
    mem[cnt].w=w;
    mem[cnt].nxt=head[u];
    head[u]=cnt;
}

int N,M;
int leaf[3005];
int f[3005][3005];

inline void dfs(int u){
    if(leaf[u]){
        f[u][1]=leaf[u];
        size[u]=1;
        return;
    }
    for(register int i=head[u];i;i=mem[i].nxt){
        int v=mem[i].v,w=mem[i].w;
        dfs(v);
        size[u]+=size[v];
        for(register int j=M;j>=1;--j)
            for(register int k=0;k<=min(size[v],j);++k)
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
    }
}

int main(){
    memset(f,0xcf,sizeof(f));
    scanf("%d%d",&N,&M);
    for(register int i=1;i<=N-M;++i){
        int k;
        scanf("%d",&k);
        for(register int j=1;j<=k;++j){
            int a,c;
            scanf("%d%d",&a,&c);
            AddEdge(i,a,c);
        }
    }
    for(register int i=1;i<=M;++i) scanf("%d",&leaf[N-M+i]);
    for(register int i=1;i<=N;++i) f[i][0]=0;
    dfs(1);
    for(register int i=M;i>=1;--i){
        if(f[1][i]>=0){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}