Luogu 1273 有线电视网 - 树形背包

Description

树形背包， 遍历到一个节点， 枚举它的每个子节点要选择多少个用户进行转移。

Code

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define rd read()

 #define R register

 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(register int i = (a); i >= (b); --i)

 using namespace std;

 const int N = 3e3 + ;

 const int inf = 1e8;

 int n, m, tot, head[N];

 int a[N], sum[N], F[N][N];

 struct edge {

     int nxt, to, val;

 }e[N];

 inline int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 inline void add(R int u, R int v, R int val) {

     e[++tot].to = v;

     e[tot].nxt = head[u];

     e[tot].val = val;

     head[u] = tot;

 }

 inline int cmax(int A, int B) {

     return A > B ? A : B;

 }

 inline void dp(R int u) {

     for(R int i = head[u]; i; i = e[i].nxt) {

         R int nt = e[i].to;

         dp(nt);

         sum[u] += sum[nt];

         per(k, sum[u], ) per(j, sum[nt], ) if(k >= j)F[u][k] = cmax(F[u][k], F[u][k - j] + F[nt][j] - e[i].val);

     }

     if(u >= n - m + ) F[u][] = a[u], sum[u] = ;

 }

 int main()

 {

     n = rd; m = rd;

     rep(i, , n - m) {

         R int cnt = rd;

         rep(j, , cnt) {

             R int u = rd, val = rd;

             add(i, u, val);

         }

     }

     rep(i, n - m + , n) a[i] = rd;

     rep(i, , n) rep(j, , m) F[i][j] = -inf;

     dp();

     per(i, m, )

         if(F[][i] >= ) return printf("%d\n", i), ;

 }