前言

此题是一道中上难度的树形背包问题。其实质其实就是01背包问题。

难点在于状态的转移以及状态转移方程，不同于其他的树形背包题目。应该说很有特点吧，十分适合初学者练练手。

没有了解过树形背包的读者可以看看我的这篇博客https://blog.****.net/weixin_44049566/article/details/88110155，这样看的时候才不会很困难。

题目

问题 J(1289): 【基础算法】有线电视网

时间限制: 1 Sec 内存限制: 64 MB

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入

第1行：2个整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。

接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下： K A1 C1 A2 C2 … Ak Ck K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。

输出

仅一行，包含一个整数，表示上述问题所要求的最大用户数。

样例输入

5 3 2 2 2 5 3 2 3 2 4 3 3 4 2

样例输出
2
提示

如图所示，共有五个结点。结点①为根结点4、2，从结点①可以传送信号到结点②，费用为2，也可以传送信号到结点⑤，费用为3（第二行数据所示），从结点②可，即现场直播站，②为一个中转站，③④⑤为用户端，共M个，编号从N-M+1到N，他们为观看比赛分别准备的钱数为3、以传输信号到结点③，费用为2。也可传输信号到结点④，费用为3（第三行数据所示），如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为： 2+3+2+3=10，大于用户愿意支付的总费用3+4+2=9，有线电视网就亏本了，而只让③④两个用户看比赛就不亏本了。

分析

此题整体并不困难，但一些细节却需要斟酌一下。

我在看到这道题的时候，关于状态转移方程，我有两种想法。

第一种

C++较复杂的树形背包问题（01背包）——有线电视网表示从根节点到当前节点i，一共还剩j元，让个人看到了电视。

但仔细想想就会发现这个方法实现起来很困难，甚至于无法实现。而我便一直在思考，最终还是没有想出来。

第二种，即正解

C++较复杂的树形背包问题（01背包）——有线电视网表示从根节点到当前节点i，一共让j个人，还剩元。（不难发现只是换了个顺序）

那么为什么第二维表示的意思不同，整个算法的实现效果也就不同呢？

让我们回忆一下，在实现背包问题时，我们普遍的规律便是从大到小枚举j，而问题的关键就是j的范围!

第一种方法，我们完全不能知道，所以实现起来很困难。而第二种，乍一看也是无法得知的。但我们可以在从叶子节点递归回来时统计所有观众数，形如如下代码：

int DP(int x) {
    if(val[x]) {//val[x]表示x有观众
        f[x][1]=val[x];//初始化一下
        return 1;
    }
    int sum=0;//总观众数
    for(int i=0;i<G[x].size();i++) {
        int v=G[x][i].v,p=DP(v);//递归统计
        sum+=p;
        DP部分，这里不予展示。
    }
    return sum;
}

这样，我们就可以得出状态转移方程

C++较复杂的树形背包问题（01背包）——有线电视网。(这里建议结合代码理解）

前面我已经说过此题的细节很多，这里给大家总结一下容易错的细节：

1. C++较复杂的树形背包问题（01背包）——有线电视网有可能是负数，所以求max的时候就不能把f数组全赋0，而是要赋一个极小值。

2.关于答案，因为我们要输出最大的"j",所以可以从大到小枚举,当大于等于0时，说明合法,直接输出j.

3.关于初始化， C++较复杂的树形背包问题（01背包）——有线电视网都要赋值成“0”；

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
  
const int N=3010;
  
struct node {
    int v,w;
    node() {};
    node(int V,int W) { v=V; w=W; }
};
 
int dis[N],n,m,f[N][N],val[N];
vector<node> G[N];
  
int DP(int x) {
    if(val[x]) {
        f[x][1]=val[x];
        return 1;
    }
    int sum=0;
    for(int i=0;i<G[x].size();i++) {
        int v=G[x][i].v,p=DP(v);
        sum+=p;
        for(int j=sum;j;j--)
            for(int k=1;k<=j;k++)
                f[x][j]=max(f[x][j],f[v][k]+f[x][j-k]-G[x][i].w);
    }
    return sum;
}
  
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1,n1,v,w;i<=n-m;i++) {
        scanf("%d",&n1);
        while(n1--) {
            scanf("%d %d",&v,&w);
            G[i].push_back( node(v,w) );
        }
    }
    for(int i=n-m+1;i<=n;i++)
        scanf("%d",&val[i]);
    memset(f,-60,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][0]=0;
    int l=DP(1);
    for(int i=l;i>=0;i--)
        if(f[1][i]>=0) {
            cout<<i;
            return 0;
        }
}

C++较复杂的树形背包问题（01背包）——有线电视网

前言

题目

问题 J(1289): 【基础算法】有线电视网

题目描述

输入

输出

样例输入

样例输出

提示

分析

代码

相关推荐