链接：http://poj.org/problem?id=1155
题意：电视台转播一场重要的足球比赛，以这个转播机器为根建立一棵“转播树”，数中一共有N个(N<=3000)，叶子节点是所有用户，有M个用户(M<=N-1)，每个用户有固定的付费额度。除了用户以外的结点都是转接信号的机器，在所有结点之间连线都需要有一定的花费。现在要求我尽可能满足更多人的观看要求，并且保证转播不赔钱。问最多可以保证多少人的观看要求。
思路：从叶到根依次记录当前结点可以满足的观看要求的数量，并且记录满足该数量的最多收益，即对每个结点进行背包DP，保证每次决策的最优化。
状态转移方程：dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]-w)，u是当前结点，v是子结点，j是u的一种可以满足的人数，k是已经从v的一种可以满足的人数，dp[v][k]已经先确定过了。w是路径的花费值。对于每个叶子结点dp[u][1]就是u可以付的费用。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x3fffffff
#define maxn 3005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int head[maxn],top,dp[maxn][maxn],t[maxn],N,M,tot,x,y,num[maxn];
void init()
{
memset(head,-1,sizeof(head));
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
dp[i][j]=-INF;
memset(t,0,sizeof(t));
memset(num,0,sizeof(num));
top=0;
}
struct Edge
{
int v,w;
int next;
} edge[maxn];
void add_edge(int u,int v,int w)
{
edge[top].v=v;
edge[top].w=w;
edge[top].next=head[u];
head[u]=top++;
}
void dfs(int u,int f)
{
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v,w=edge[i].w;
if(v!=f)
{
dfs(v,u);
num[u]+=num[v];
for(int j=num[u]; j>=1; j--)
for(int k=1; k<=min(j,num[v]); k++)
if(dp[v][k]!=-INF)
dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]-w);
}
}
}
int main()
{
scanf("%d%d",&N,&M);
init();
for(int i=1; i<=N-M; i++)
{
scanf("%d",&tot);
for(int j=1; j<=tot; j++)
{
scanf("%d%d",&x,&y);
add_edge(i,x,y);
}
}
for(int i=N-M+1; i<=N; i++)
{
scanf("%d",&dp[i][1]);
num[i]=1;
}
dfs(1,1);
for(int i=num[1]; i>=0; i--)
if(dp[1][i]>=0)
{
printf("%d\n",i);
break;
}
return 0;
}