[洛谷P1273] 有线电视网

类型：树形背包

传送门：>Here<

题意：给出一棵树，根节点在转播足球赛，每个叶子节点是一个观众在收看。每个叶子结点到根节点的路径权值之和是该点转播的费用，每个叶子节点的观众都会付val[i]的钱。先问在不亏本的前提下，最多转播多少观众

解题思路

$dp[u][i][j]$表示在以$u$为根节点的子树内，前$i$棵子树内选择$j$名观众的最大收益。这里的收益指的就是【所选观众交的钱 - 从$u$出发的转播费用总和】。从$u$出发就是指$u$以上的转播费用都不算

因此容易得到$dp[u][i][0]=0$（任何一个点不转播的收益都是0），为了一会儿打擂，其他权且置为$-∞$

在讲状态转移之前，先来回顾一下分组背包问题——物品已经分为几个组，题目要求每个组只能选择一个物品，使总价值最大。表面上看上去有点棘手，实际上就是一个01背包，只不过加了限定，一个组里只能选一个物品。因此正常的做法是遍历每一组，然后选择即可

那么当前这个问题可以转化为分组背包模型——每棵子树为一组，每组只能选择一个"物品"。这里的一组里的每个物品也就是"1个观众，2个观众，……"

因此易得转移方程$$dp[u][i][j]=Max{dp[u][i-1][j-k] + dp[v][numson[v]][k] - cost[u ightarrow v]}$$注意要减去到达$v$的这一条边的费用。其中$numson[v]$是指$v$的直接儿子数量

观察可以发现$i$这一维可以滚动，因此可以优化为$$dp[u][j]=Max{dp[u][j-k] + dp[v][k] - cost[u ightarrow v]}$$但是注意$j$要由$j-k$转移，因此$j$应当倒着扫。那$numson[v]$这一维可以舍去？因为$v$已经做完了，所以自然指的就是$numson[v]$了。

至于答案输出，我们只需要看$dp[1][q]$中满足$dp[1][q] geq 0$的最大$q$就好了

Code

读入卡了我半天，这题的读入真奇特

/*By DennyQi 2018.8.14*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define  r  read()
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = 3010;
const int MAXM = 6010;
const int INF = 1061109567;
inline int read(){
    int x = 0; int w = 1; register int c = getchar();
    while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w;
}
int N,M,R,x,y,K,ans;
int first[MAXM],nxt[MAXM],to[MAXM],cost[MAXM],num_edge;
int val[MAXN],dp[MAXN][MAXN],size[MAXN];
inline void add(int u, int v, int w){
    to[++num_edge] = v,cost[num_edge] = w,nxt[num_edge] = first[u],first[u] = num_edge;
}
int DP(int u, int _f){
    int v,isleaf=1,tot=0;
    if(u > N-M){ dp[u][1] = val[u]; return 1; }
    for(int i = first[u]; i; i = nxt[i]){
        if((v = to[i]) == _f) continue;
        tot += DP(v, u);
        for(int j = tot; j; --j)
            for(int k = 1; k <= j; ++k)
                dp[u][j] = Max(dp[u][j], dp[u][j-k] + dp[v][k] - cost[i]);
    }
    return tot;
}
int main(){
    memset(dp, -0x3f, sizeof(dp));
    N = r, M = r;
    for(int i = 1; i <= N-M; ++i){
        K = r;
        for(int j = 1; j <= K; ++j){
            x = r, y = r;
            add(i, x, y), add(x, i, y);
        }
    }
    for(int i = 1; i <= N; ++i) dp[i][0] = 0;
    for(int i = N-M+1; i <= N; ++i) val[i] = r;
    DP(1, -1);
    for(int i = 0; i <= M; ++i) if(dp[1][i] >= 0) ans = Max(ans, i);
    printf("%d", ans);
    return 0;
}