题目意思：
电视台发送信号给很多用户，每个用户愿意出一些钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。
多么明显的有依赖性的01背包：
dp[i][j]对于借点I 背包容量J ；
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn=3004;
const int INF=0x7ffffff;
struct Edge
{
int to,dis,pre;
Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}
};
Edge edge[maxn];
int head[maxn],pos;
int money[maxn];
int dp[maxn][maxn];
void inint()
{
memset(head,-1,sizeof(head));
pos=0;
}
void add_edge(int &s,int &to,int &dis)
{
edge[pos]=Edge(to,dis,head[s]);
head[s]=pos++;
}
int n,m;
int dfs(int s)
{
int ans=0,key;
dp[s][0]=0;
for(int i=1;i<maxn;i++)dp[s][i]=-INF;
for(int i=head[s];i!=-1;i=edge[i].pre)
{
Edge &tmp=edge[i];
if(tmp.to==-1) key=0;
else key=dfs(tmp.to);
ans+=key;
for(int j=ans;j>=1;j--)
for(int t=1;t<=key;t++)
{
if(j<t)break;
dp[s][j]=max(dp[s][j],dp[s][j-t]+dp[tmp.to][t]-tmp.dis);
}
}
if(s>(n-m))
{
ans++;
for(int j=ans;j>=1;j--) dp[s][j]=dp[s][j-1]+money[s];
}
return ans;
}
int main()
{
int num,a,b;
while(~scanf("%d%d",&n,&m))
{
inint();
for(int i=1;i<=(n-m);i++)
{
scanf("%d",&num);
for(int w=1;w<=num;w++)
scanf("%d%d",&a,&b),
add_edge(i,a,b);
}
for(int i=n-m+1;i<=n;i++)scanf("%d",&money[i]);
dfs(1);
for(int i=n;i>=0;i--)
if(dp[1][i]>=0){printf("%d
",i);break;}
}
return 0;
}