记录编号	165988	评测结果	AAAAAAAAAA
题目名称	1189.有线电视网	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2015-06-13 19:33:03	内存使用	31.42 MiB

/*========================
TYPE:
TITLE:
COPYRIGHT:MOSHANGYIN
========================*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int size;
int n, m;
int val[3010],head[3010];
int f[3010][3010];
struct Node
{
	int v, next, w; 
}e[3010];
void addedge(int u,int v,int w)
{
	e[size].v=v;
	e[size].w=w;
	e[size].next=head[u];
	head[u]=size++;
}
int dfs(int u) 
{
	for (int i = 1; i <= m; ++i)
	{
		f[u][i] = -0x3F3F3F3F;
	}
	if (head[u] == 0) 
	{
		f[u][1] = val[u];
		return 1;
	}  
	int sum = 0;
	for (int m = head[u]; m ; m = e[m].next) 
	{
		int v = e[m].v, w = e[m].w;
    	int numLeaf = dfs(v);
		sum += numLeaf;
		for (int s = sum; s >= 1; --s) 
		{
			for (int k = 0; k <= numLeaf && k <= s; ++k)
			{
				f[u][s] = max(f[u][s], f[u][s-k] + f[v][k] + w);
			}
		}
	}
	return sum;
}
int main()
{
	freopen("televi.in","r",stdin);
	freopen("televi.out","w",stdout);
	scanf("%d%d",&n,&m);
	size=1;
	for(int i=1;i<=n-m;i++)
	{
		int x,v,w;
		scanf("%d",&x);
		while(x--)
		{
			scanf("%d%d",&v,&w);
			addedge(i,v,-w);
		}
	}
	for (int i = n - m + 1; i <= n; ++i) 
	{
		scanf("%d", &val[i]);
	}
	dfs(1);
	for (int i = m; i >= 0; --i)
	{
		if (f[1][i] >= 0) 
		{
			printf("%d",i);
			break;
		}
	}
}