1、http://poj.org/problem?id=1155
2、题目大意：
有n台电视，其中这n台电视中有n-m台是服务器，有m台式用户，现在已知每条线路的代价值，又知道每个用户想给服务器的钱数，在电视台不亏损的前提下，最多可以让多少用户接收到信号
分析：
这是一道树形DP的问题，首先定义状态dp[i][j]表示以i为根节点j个用户的最大收益
那么我们要求最多的用户数，只要在i={0-m}个用户个数中，找到使得dp[1][i]>=0的这个i值即可
假设fa是当前的父节点，v是fa的子节点，那么dp[fa][j]=max(d[fa][j],dp[fa][j-k]+dp[v][k]-w[fa][v])
以fa为根节点的j个用户的最大收益就等于以fa的子节点为根的k个再加上以fa为根的j-k个和
-w[i][j]是因为当前选中fa的子节点v，那么fa到v的这条边就得加上，只不过这是电视台的消费，所以为负值
另外需要一个tmp[j]数组来记录dp[fa][j],优化
3、AC代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 3005
#define INF 0x7fffffff
int v[N];
int w[N];
int head[N];
int next[N];
int tot=0;
int dp[N][N];
int num[N];
int tmp[N];
void add_edge(int a,int b,int c)
{v[tot]=b;w[tot]=c;next[tot]=head[a];head[a]=tot++;
}
void dfs(int fa)
{for(int i=head[fa];i!=-1;i=next[i]){int vv=v[i];dfs(vv);for(int j=0;j<=num[fa];j++)tmp[j]=dp[fa][j];for(int j=0;j<=num[fa];j++){for(int k=1;k<=num[vv];k++){dp[fa][j+k]=max(dp[fa][j+k],tmp[j]+dp[vv][k]-w[i]);}}num[fa]+=num[vv];}
}
int main()
{int n,m,k,a,b;scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));for(int i=1;i<=n-m;i++){num[i]=0;scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d%d",&a,&b);add_edge(i,a,b);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)dp[i][j]=-INF;}for(int i=n-m+1;i<=n;i++){scanf("%d",&dp[i][1]);num[i]=1;}dfs(1);for(int i=m;i>=0;i--){if(dp[1][i]>=0){printf("%d\n",i);break;}}return 0;
}