洛谷P1273 有线电视网

庆祝第100篇文章完成！

题意

一棵有边权的树，有的节点是转播站，有的节点是用户节点。要让用户看到电视，代价为根节点到当前用户节点的路径和，重复的路径不重新计算。每个用户可以支付一定的钱。

求在不亏本的情况下，最多可以让多少个用户看到电视。

其中点数 $N\le 3000$ 。

题解

树上背包的裸题。

用 $f[x][i]$ 表示在以 $x$ 节点为根的子树中选 $i$ 个用户的最大收益。转移方程式为：

$$f[x][i]=max(f[x][i],f[y][j]+f[x][i-j]-w(x,y)) \ , \ j\le i$$

其中 $w(x,y)$ 为点 $x$ 和 $y$ 之间的边权。

最后从大到小枚举，只要不亏本就输出。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[3005];
int cnt,head[3005],n,m,a,b,c,f[3005][3005],siz[3005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    siz[x]=1;
    if (x>n-m) return;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        dfs(y);
        siz[x]+=siz[y];
        for (int j=siz[x]-1;j;j--)
            for (int k=1;k<=min(j,siz[y]);k++)
                f[x][j]=max(f[x][j],f[y][k]+f[x][j-k]-w);
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n-m;i++)
    {
        a=read();
        while (a--)
        {
            b=read(); c=read();
            add(i,b,c);
        }
    }
    memset(f,-0x3f,sizeof(f));
    for (int i=n-m+1;i<=n;i++) f[i][1]=read();
    for (int i=1;i<n;i++) f[i][0]=0;
    dfs(1);
    int ans=m;
    while (f[1][ans]<0 && ans>0) ans--;
    return !printf("%d",ans);
}