[洛谷P1273]有线电视网
/ / 阅读耗时 12 分钟很不容易独立A出的一道题，做做纪念。
难度：提高+/省选-
题目描述
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
输入输出格式
输入格式:
输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。
第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：
K A1 C1 A2 C2 … Ak Ck
K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。
输出格式:
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
输入输出样例
Sample input
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
Sample output
2
说明
[样例解释]
如图所示，共有五个结点。结点①为根结点，即现场直播站，②为一个中转站，③④⑤为用户端，共M个，编号从N-M+1到N，他们为观看比赛分别准备的钱数为3，4，2，从结点①可以传送信号到结点②，费用为2，也可以传送信号到结点⑤，费用为3(第二行数据所示)，从结点②可以传输信号到结点③，费用为2。也可传输信号到结点④，费用为3(第三行数据所示)，如果要让所有用户(③④⑤)都能看上比赛，则信号传输的总费用为:2+3+2+3=10，大于用户愿意支付的总费用3+4+2=9，有线电视网就亏本了，而只让③④两个用户看比赛就不亏本了。
题解
本题实际上在考察树上的分组背包DP问题，属于树型DP。这里先介绍一种转二叉树的方法。
首先注意到题目没有给定价格和边权的数据范围，若以此为依据DP，连数组范围都难以确定。于是不妨令dp(r，k)表示以r为根的子树中满足k个用户时可以得到的最大收益，这样状态就可以得到确定，答案即为使dp(1，k)为非负时的最大k(假设1是整棵树的根)。
但是这样状态转移会很难写，因为需要把这k个用户分配给其子树，这显然有很多情况，是难以分配的。但是注意到二叉树很容易分配，于是考虑转多叉树为二叉树的方法。
首先认清一个事实，以下两棵树是等价的。
这里新建了一个节点和一条边，并令这条边的边权为0，这样就把三叉树转成了一棵等价的二叉树。其余如四叉树等的转法与之同理。
预处理出每一个节点所含的叶子节点数child(i)，DP时严格保证dp(r，k)中k≤child(r)，这样状态转移方程就可以列出:
对于任何节点i，dp(i，0)=0。
- 若i为叶子节点，则dp(i，1)=money(i)，即这个用户支付的费用。
- 若i有一个儿子，则dp(i，k)=dp(c1，k)-v1。c1为儿子节点，v1为到儿子的边的边权。
- 若i有两个儿子，则需要进行分配。
如果k=child(c1)+child(c2)，则不需进行分配，直接结果就是
如果k<child(c1)+child(c2):
对只分配给一棵子树的情况需要之后另行特判。
若k≤child(c1)，则:
若k≤child(c2)。则:
根据状态转移方程推出结果即可，这种方法其实很快。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
int head[NUM], to[NUM], nxt[NUM], value[NUM], child[NUM] = {0};
int money[3000];
int dp[NUM][3000] = {0};
int cnt = 1, ncnt = 0;
int N, M;
inline void add(int x, int y, int z) {
nxt[cnt] = head[x], to[cnt] = y, value[cnt] = z, head[x] = cnt++;
}
int DFS(int x) {
for (int i = head[x]; i != -1; i = nxt[i])child[x] += DFS(to[i]);
if (child[x] == 0)return child[x] = 1;
return child[x];
}
int DP(int root, int n) {
if (n == 0)return 0;
if (dp[root][n] > -1e7)return dp[root][n];
int l1, l2;
if (head[root] == -1)return dp[root][n] = money[root];
l1 = to[head[root]];//左儿子
if (nxt[head[root]] == -1)return dp[root][n] = DP(l1, n) - value[head[root]];
l2 = to[nxt[head[root]]];//右儿子
if (n == child[root])return dp[root][n] = DP(l1, child[l1]) + DP(l2, child[l2]) - value[head[root]] - value[nxt[head[root]]];
if (child[l1] >= n)dp[root][n] = max(dp[root][n], DP(l1, n) - value[head[root]]);
if (child[l2] >= n)dp[root][n] = max(dp[root][n], DP(l2, n) - value[nxt[head[root]]]);
for (int i = max(1, n - child[l2]); i <= child[l1] && i < n; i++)dp[root][n] = max(dp[root][n], DP(l1, i) + DP(l2, n - i) - value[head[root]] - value[nxt[head[root]]]);
return dp[root][n];
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
ncnt = N + 1;
memset(head, -1, sizeof(head));
for (int i = 1; i <= N - M; i++) {
int x;
cin >> x;
if (x <= 2) {
for (int j = 1; j <= x; j++) {
int a, b;
cin >> a >> b;
add(i, a, b);
}
} else {
int from = i;
for (int j = 1; j <= x; j++) {
int a, b;
cin >> a >> b;
add(from, a, b);
if (j <= x - 2)add(from, ncnt, 0), from = ncnt++;//转二叉树
}
}
}
for (int i = N - M + 1; i <= N; i++)cin >> money[i];
DFS(1);
for (int i = 1; i < ncnt; i++) {
for (int j = 0; j <= child[i]; j++)dp[i][j] = static_cast<int>(-1e8);
}
for (int i = M; i >= 0; i--) {
if (DP(1, i) >= 0) {
cout << i;
return 0;
}
}
}