P1273 有线电视网 • CoderXL's Blog

树形 DP $\times$ 背包

不难看出，整个电视转播网络是一个数，叶子节点是用户。

而树上的最优子结构清晰明了——更大的子树的最优解来自小的子树的最优解，是非常好 DP 的。

对于本题，最优解就是最大用户数/最大利润。

问题在于，我们要设计什么状态。细想一下这题求解的目标其实类似背包 DP. 限制利润不能为负，最大化用户数。乍一看，应该设计 $dp[i][p]$ ，表示以 $i$ 为根的子树，利润为 $p$ 时，用户数最大是多少。最后对根扫一遍所有非负的 $p$ 中，用户数的最大值。

这样做是可以的，但是由于利润的值域较大，并且要维护负利润，因此转移复杂度高，无法通过。

而实际上，这道题有两种状态设计的方法，另一种就是以用户数 $u$ 作为状态， $dp[i][u]$ 表示以 $i$ 为根的子树，用户数为 $u$ 时，利润最大是多少。

这样，由于 $u$ 始终非负且值域较小，转移复杂度更低。随后只需要在根上求出 $\displaystyle{\max_{dp[root][u] \ge 0} u }$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Edge
{
    int to;
    int l;
    int next;
}edge[5000];
int cnt;
int head[5000];
int f[5000][5000];
void add(int a,int b,int l)
{
    cnt++;
    edge[cnt].to=b;
    edge[cnt].l=l;
    edge[cnt].next=head[a];
    head[a]=cnt;
}
int dfs(int p)
{
    if(p>n-m)
        return 1;
    int sum=0;
    for(int i=head[p];i;i=edge[i].next)
    {
        int q=edge[i].to;
        int l=edge[i].l;
        int t=dfs(q);
        sum+=t;
        for(int j=sum;j>=1;j--)
        {
            for(int k=1;k<=t;k++)
            {
                f[p][j]=max(f[p][j],f[p][j-k]+f[q][k]-l);
            }
        }
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n-m;i++)
    {
        int c;
        cin>>c;
        for(int j=1;j<=c;j++)
        {
            int a,l;
            cin>>a>>l;
            add(i,a,l);
        }
    }
    memset(f,128,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        f[i][0]=0;
    }
    for(int i=n-m+1;i<=n;i++)
    {
        cin>>f[i][1];
    }
    dfs(1);
    for(int i=m;i>=0;i--)
    {
        if(f[1][i]>=0)
        {
            cout<<i;
            break;
        }
    }
    return 0;
}

cpp