Luogu 1273 有线电视网

Description

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

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define rd read()
 5 #define R register
 6 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
 7 #define per(i,a,b) for(register int i = (a); i >= (b); --i)
 8 using namespace std;
 9 
10 const int N = 3e3 + 4;
11 const int inf = 1e8;
12 
13 int n, m, tot, head[N];
14 int a[N], sum[N], F[N][N];
15 
16 struct edge {
17     int nxt, to, val;
18 }e[N];
19 
20 inline int read() {
21     int X = 0, p = 1; char c = getchar();
22     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
23     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
24     return X * p;
25 }
26 
27 inline void add(R int u, R int v, R int val) {
28     e[++tot].to = v;
29     e[tot].nxt = head[u];
30     e[tot].val = val;
31     head[u] = tot;
32 }
33 
34 inline int cmax(int A, int B) {
35     return A > B ? A : B;
36 }
37 
38 inline void dp(R int u) {
39     for(R int i = head[u]; i; i = e[i].nxt) {
40         R int nt = e[i].to;
41         dp(nt);
42         sum[u] += sum[nt];
43         per(k, sum[u], 0) per(j, sum[nt], 1) if(k >= j)F[u][k] = cmax(F[u][k], F[u][k - j] + F[nt][j] - e[i].val);
44     }
45     if(u >= n - m + 1) F[u][1] = a[u], sum[u] = 1;
46 }
47 
48 int main()
49 {
50     n = rd; m = rd;
51     rep(i, 1, n - m) {
52         R int cnt = rd;
53         rep(j, 1, cnt) {
54             R int u = rd, val = rd;
55             add(i, u, val);
56         }
57     }
58     rep(i, n - m + 1, n) a[i] = rd;
59     rep(i, 1, n) rep(j, 1, m) F[i][j] = -inf;
60     dp(1);
61     per(i, m, 0) 
62         if(F[1][i] >= 0) return printf("%d
", i), 0;
63 }
View Code