记录编号	166049	评测结果	AAAAAAAAAA
题目名称	有线电视网	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2015-06-14 08:56:48	内存使用	42.77 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define fi first
#define se second
#define inf 0xfffffff
#define maxn 3333
#define PII pair<int, int>
int n,m,k,x,y,e,st[maxn],ed[maxn],val[maxn],dp[maxn][maxn],sum[maxn];
PII edge[maxn];

bool cmp(PII a, PII b){
return sum[a.fi]>sum[b.fi];
}

void dfs(int x){
if (x>n-m){
sum[x]=1;
dp[x][1]=val[x];
return;
    }

for (int i=st[x]; i<ed[x]; i++)dfs(edge[i].fi);

sort(&edge[st[x]],&edge[ed[x]],cmp);

dp[x][0]=0;
for (int i=1; i<=sum[edge[st[x]].fi]; i++)
dp[x][i]=max(dp[x][i],dp[edge[st[x]].fi][i]-edge[st[x]].se);

sum[x]=sum[edge[st[x]].fi];
for (int i=st[x]+1; i<ed[x] && (sum[x]+=sum[edge[i].fi]); i++)
for (int j=sum[x]; j; j--)
for (int k=1; k<=j&& k<=sum[edge[i].fi]; k++)
dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[edge[i].fi][k]-edge[i].se);

}

int main(){
	freopen("televi.in", "r", stdin);
	freopen("televi.out", "w", stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=n-m; i++){
scanf("%d",&k);
st[i]=e;
for (int j=0; j<k; j++){
scanf("%d%d",&x,&y);
edge[e].fi=x;
edge[e++].se=y;
        }
ed[i]=e;
    }
for (int i=n-m+1; i<=n; i++)scanf("%d",&val[i]);
for (int i=0; i<=n; i++)
for (int j=0; j<=m; j++)
dp[i][j]=-inf;
dfs(1);
for (int i=m; i+1; i--)
if (dp[1][i]>=0){
printf("%d\n",i);
break;
        }
	fclose(stdin);
	fclose(stdout);
return 0;
}