首页技术正文

【题解】洛谷P1273 有线电视网（树上分组背包）

开发者沁仪技术 2022年11月9日

0 收藏 950 点赞 4,387 浏览 1169 个字

次元传送门：洛谷P1273

思路

一开始想的是普通树形DP 但是好像实现不大好

观摩了一下题解

是树上分组背包

设f[i][j]为以i为根的子树中取j个客户得到的总价值

我们可以以i为根有j组

在每一组中分别又取1个，2个，3个……n个客户

化为背包思想即 j为一共有j组 背包容量为每组的客户数总和把该节点的每个儿子看成一组每组中的元素为选一个，选两个…选n个用户

状态转移方程：

f[i][j]=max(f[i][j],f[i][j-k]+f[v][k]-边权);//i为根 j为容量

最后输出f[1][i]>=0的i的最大值 所以反向枚举

代码

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 3010
#define INF 1e9+7
int f[maxn][maxn];
int h[maxn],val[maxn];
int n,m,cnt;
struct Edge
{
    int to;
    int next;
    int w;
}e[maxn*maxn];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=h[u];
    h[u]=cnt;
}
int dfs(int u)
{
    if(u>n-m)//如果是叶子节点
    {
        f[u][]=val[u];//当前只能取一个客户 就是自己
        return ;//返回几个客户
    }
    int t,sum=;//t为当前组有几个客户 sum为背包容量
    for(int i=h[u];i;i=e[i].next)//枚举组
    {
        int v=e[i].to;
        t=dfs(v);
        sum+=t;
        for(int j=sum;j>=;j--)//枚举容量 倒序
            for(int k=;k<=t;k++)//枚举客户数量
            {
                if(j-k>=) f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w);
                //满足背包容量大于客户数量才可以
            }
    }
    return sum;
}
int main()
{
    memset(f,~0x3f,sizeof(f));//初始化为一个极小负数 因为可能有负数
    cin>>n>>m;
    for(int i=;i<=n-m;i++)
    {
        int size;
        cin>>size;
        for(int j=;j<=size;j++)
        {
            int x,y;
            cin>>x>>y;
            add(i,x,y);
        }
    }
    for(int i=n-m+;i<=n;i++) cin>>val[i];
    for(int i=;i<=n;i++) f[i][]=;//初始化 取0个客户的花费为0
    dfs();
    for(int i=m;i>=;i--)//反向枚举
    {
        if(f[][i]>=)
        {
            cout<<i;
            return ;
        }    }
}