POJ 1155 经典树形dp+分组背包 + 模板

题意：电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。
dp[i][j]代表i节点为根节点的子树j个用户的时候最大剩余费用。
dp[i][j] = max(dp[i][j], dp[i][k]+dp[son][j-k]-w[i][son]);

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3e3+7;
int n,m,num,head[maxn],c[maxn],dp[maxn][maxn];
struct list1{int u,v,w,next;}a[maxn];
void add(int u,int v,int w){a[num]={u,v,w,head[u]};head[u]=num++;}
void dfs(int u)
{int i,j,k,v,w;for(i=head[u];~i;i=a[i].next){v=a[i].v;w=a[i].w;dfs(v);c[u]+=c[v];for(j=c[u];j>0;j--)              //注意循环从后往前，防止相互影响(类似于背包)for(k=1;k<=j;k++)dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]-w);}
}
int main()
{int i,j,v,w,x;while(~scanf("%d%d",&n,&m)){for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(!j) dp[i][j]=0;else dp[i][j]=-1000000;memset(head,-1,sizeof(head));memset(c,0,sizeof(c));num=1;for(i=1;i<=n-m;i++){scanf("%d",&x);for(j=1;j<=x;j++) scanf("%d%d",&v,&w),add(i,v,w);}for(i=n-m+1;i<=n;i++) scanf("%d",&dp[i][1]),c[i]=1;dfs(1);for(i=m;i>=0;i--) if(dp[1][i]>=0) break;printf("%d\n",i);}return 0;
}