luogu P1273 有线电视网

原题链接：https://www.luogu.org/problem/show?pid=1273

题外话：luogu的试炼场，棋盘制作与地精部落两道省选题就不说了，其他的三道题也都这么难，这道题对于树形DP刚入门的蒟蒻来说实在是不友好，于是求助于题解，终于A掉此题。

本题的有趣的地方就在于，最后只需保证不赔本即可，所以，即使有的用户，愿意付出的钱比使他收到信号花费的钱要少，但是如果在别的用户的身上赚到了更多钱，也有可能让其收到信号，也就是说，并不能只使用贪心来解决此题，可能会丢失最优解。

与其他树形DP基本相似的框架，读入，预处理（本题一定要预处理，因为在有的用户的收益可能是负的，所以要预先填充一个极小的数字。），邻接表存边。本题比较友好的地方是，已知那些点是用户，而且有确定的根。

f[i][j]表示以i为根节点的树，子树中选j个用户让其收到信号时的最大收益（尽管最大收益也可能是负的），设子节点为t（不止一个），便有转移方程：f[x][j]=max(f[x][j],f[x][j-k]+f[t][k]-e[i].w);如果这是用户节点，可以直接返回。

最后由m到1枚举，当f[1][i]>=0时，i便是最后的答案。

#include<cstdio>
#include<cstring>
void read(int &y)
{
    y=0;char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9')
    {
        y=y*10+x-'0';
        x=getchar();
    }
}
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int f[3005][3005],head[3005];
int n,m,cnt,p[3005];
struct edge
{
    int u,v,w;
}e[10005];
void add(int u,int v,int w)
{
    e[++cnt].u=head[u];
    e[cnt].v=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int dp(int x)
{
    if(x>n-m)
    {
        f[x][1]=p[x];
        return 1;
    }
    int sum=0;
    for(int i=head[x];i;i=e[i].u)
    {
        int t=e[i].v,a=dp(t);
        sum+=a;
        for(int j=sum;j>0;j--)
        {
            for(int k=1;k<=a;k++) f[x][j]=max(f[x][j],f[x][j-k]+f[t][k]-e[i].w);
        }
    }
    return sum;
}
int main()
{
    memset(f,-63,sizeof(f));
    read(n);read(m);
    for(int i=1;i<=n-m;i++)
    {
        int k,v,w;
        read(k);f[i][0]=0;
        for(int j=1;j<=k;j++)
        {
            read(v);read(w);
            add(i,v,w);
        }
    }
    for(int i=n-m+1;i<=n;i++)
    {
        read(p[i]);
        f[i][0]=0;
    }
    dp(1);
    for(int i=m;i>0;i--)
    {
        if(f[1][i]>=0)
        {
            printf("%d",i);
            return 0;
        }
    }
    printf("0");
    return 0;
}