标签：sz int 有线电视 dfs -- P1273

P1273 有线电视网

树上背包的变形

\[f_{u, j + k} = \max_{v \in son(u)} f_{u, j} + f_{v, k} - w_{u,v} \]

这里写成 \(j + k\) 是为了和代码一致。

\(f_{u,j + k}\) 代表以 \(u\) 为根的子树中，选择了 \(j + k\) 个叶子结点的利润最大值。

\(w_{u, v}\) 代表 \(u\) 到 \(v\) 的边权。

然后就是很朴素的树上背包了，注意维护的是利润的最大值，有负数出现，需要初始化一下，详细见代码。

int n, m, w[N];
int sz[N], f[N][N], tmp[N], dep[N];
vector<pair<int, int>> e[N];
void dfs(int u)
{
    if(u >= n - m + 1)
    {
        f[u][1] = w[u];
        sz[u] = 1;
        return;
    }
    sz[u] = 0;
    for(auto [v, w] : e[u])
    {
        dfs(v);
        for(int i = 0; i <= sz[u] + sz[v]; i++)
            tmp[i] = f[u][i];
        for(int i = 0; i <= sz[u]; i++)
            for(int j = 0; j <= sz[v]; j++)
                tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] - w);
        sz[u] += sz[v]; 
        for(int i = sz[u]; i >= 0; i--)
            f[u][i] = tmp[i];   
        // for(int i = sz[u]; i >= 0; i--)
        // {
        //     cout<<"U: "<<u<<"  V: "<<v<<"  sz[u]: "<<i<<"   f_u_sz: "<<f[u][i]<<'\n';
        // }
    }
}
void solve()
{       
    cin>>n>>m;
    for(int i = 1; i <= n - m; i++)
    {
        int k;  cin>>k;
        for(int j = 1; j <= k; j++)
        {
            int v, k;   cin>>v>>k;
            e[i].push_back({v, k});
        }
    }
    for(int i = n - m + 1; i <= n; i++)
        cin>>w[i];
    for(int i = 1; i <= n; i++)
    {
        f[i][0] = 0;
        for(int j = 1; j <= n; j++)
            f[i][j] = -inf;
    }

    dfs(1);
    for(int i = m; i >= 0; i--)
    {
        if(f[1][i] >= 0)
        {
            cout<<i<<'\n';
            return;
        }
    }
    return;
}

标签：sz,int,有线电视,dfs,--,P1273
From： https://www.cnblogs.com/magicat/p/17593730.html