题目链接:传送门

Description

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。 写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

Solution

又是一道树形DP题 设

TeX parse error: Undefined control sequence \[

表示以第x个节点为根的子树中选j个用户所能获得的最大收益 于是我们有：

TeX parse error: Undefined control sequence \[

to[i]为x的儿子 w[i]为i到x的边权 然后我们枚举j和k即可 要注意j和k枚举的范围（详见代码）

Code

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define begin Begin
#define next Next
using namespace std;
const int maxn=3000+10;
int e,begin[maxn],to[maxn*2],next[maxn*2],w[maxn*2];
int money[maxn];
inline void add(int x,int y,int z){
    to[++e]=y;
    next[e]=begin[x];
    begin[x]=e;
    w[e]=z;
}
int n,m,f[maxn][maxn];
inline int dfs(int x){
    if(x>n-m){
        f[x][1]=money[x];
        return 1;
    }
    int son=0;
    for(int i=begin[x];i;i=next[i]){
        int y=dfs(to[i]);son+=y;
        for(int j=son;j>=1;j--)
            for(int k=1;k<=y;k++)
                f[x][j]=max(f[x][j],f[x][j-k]+f[to[i]][k]-w[i]);
    }
    return son;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=(n-m);i++){
        int k,x,y;
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            scanf("%d%d",&x,&y);    
            add(i,x,y);
        }
    }
    for(int i=(n-m+1);i<=n;i++)scanf("%d",&money[i]);
    memset(f,-60,sizeof(f));
    for(int i=1;i<=n;i++)f[i][0]=0;
    dfs(1);
    for(;m;m--)if(f[1][m]>=0)break;
    cout<<m<<endl;
    return 0;
}