题解 P1273 【有线电视网】

· · 题解

这是我做的第一道树上背包问题，写篇题解总结一下。如果我写的哪里不对，欢迎指出。

关于题意

讨论区里有人想用简单的贪心做（当然错了），原因是没有读清题。

题目要求的是用户最多，不亏本只是限定条件，而不是要求收益最大。

这样一来，难度提高了一些。

状态定义

先设 f_{u} 表示以 u 为根的子树，在不亏本的情况下最多能播给多少用户。

但是由于转播需要费用，所以本来不亏本的可以变得亏本，本来亏本的加上另一棵子树可以不亏本，状态定义得不好。

看来得再加一维。谁也不会想加一个费用的维度（因为值域太大），需要加用户数的维度。

设 f_{u,j} 表示以 u 为根的子树，转播给 j 个用户，最大收益是多少。

状态没问题了，但是转移太麻烦了：你得把 j 分成许多份，对于每种分法分别求和，取最值。

于是再加一维：设 f_{i,u,j} 表示以 u 为根的子树，仅用前 i 棵子树，转播给 j 个用户，最大收益是多少。

状态转移

这就要用到背包了。据说是分组背包，不管什么背包会用就行，其实是我太菜了不知道。

设第 i 棵子树转播给了 k 个用户，第 i 棵子树的根是 v，v 有 sv 个子结点。

可以得到转移式：

\large f_{i,u,j}=\max(f_{i-1,u,j-k}+f_{sv,v,k}-\mathtt{cost})

枚举 k，取最大值，就能得到答案。

优化

要是真写出来，就会发现，f 数组开不下。于是想到用滚动数组滚掉 i 维。

\large f_{u,j}=\max(f_{u,j-k}+f_{v,k}-\mathtt{cost})

但是真能说滚就滚吗？这里 f_{u,j-k} 其实已经是 f_{i,u,j-k} 了，而不是 f_{i-1,u,j-k}，

所以对于每个 i，要先备份一下再计算。

限定

设 sum 为前 i 棵子树的总用户数（不包括转播点），cnt 为第 i 棵子树的用户数。

- 首先，$k$ 应该位于 $[0,cnt]$； - $k$ 应小于等于 $j$； - $k$ 不能太小，把过多的用户“推卸”给前 $i-1$ 棵子树，整理得 $k\ge j+cnt-sum$。 得到 $\max(0,j+cnt-sum)\le k\le\min(cnt,j)

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h>
using namespace std;
struct Edge{
    int to,val;//to 是终点，val 是开销
    Edge(int t,int v)//构造函数
    { to=t;val=v; }
};
vector<Edge>edge[3010];
int n,m,f[3010][3010],v[3010],t[3010];
//f 意义同上面的推导，v 是用户愿意给的钱，t 是备份数组
int dfs(int u=1){//返回值是子树的用户数
    if(u>n-m)//递归边界
    { f[u][1]=v[u];return 1; }
    int sum=0;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i].to;
        int cnt=dfs(v);
        sum+=cnt;//cnt, sum 意义同上推导，这里 sum 累加 cnt
        for(int j=1;j<=sum;j++)t[j]=f[u][j];//备份
        for(int j=0;j<=sum;j++)
            for(int k=max(0,j+cnt-sum);k<=min(cnt,j);k++)//k 复杂的范围
                f[u][j]=max(f[u][j],t[j-k]+f[v][k]-edge[u][i].val);//转移式
    }
    return sum;
}
int main(){
    memset(f,128,sizeof f);
    //结果可能为负，所以初始化为绝对值很大的负数，用到了补码的原理
    cin>>n>>m;
    for(int i=1;i<=n-m;i++){
        int k;cin>>k;
        for(int j=1;j<=k;j++){
            int to,val;
            cin>>to>>val;
            edge[i].push_back(Edge(to,val));//直接使用构造函数
        }
    }
    for(int i=n-m+1;i<=n;i++)
        cin>>v[i];
    dfs();
    for(int i=m;i>=0;i--)
        if(f[1][i]>=0)
        { cout<<i<<endl;return 0; }
        //从多到少枚举用户数，若不亏本，直接输出
    return 0;
}