记录编号	445032	评测结果	AAAAAAAAAA
题目名称	凯伦和超市	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.673 s
提交时间	2017-09-04 21:16:38	内存使用	191.58 MiB

#include <fstream>
#include <vector>
using namespace std;
ifstream cin("market.in");
ofstream cout("market.out");
int n,b,inf = 99999999;
int c[5005],d[5005],x[5005];
int f[5005][5005],g[5005][5005];
vector <int> v[5005];
int siz[5005],h[5005];
void dfs(int u)
{
	siz[u] = 1;
	int i,w,j,k;
	
	for(i = 1;i <= n;i++)
	{
		f[u][i] = g[u][i] = inf;
	}
	f[u][1] = c[u] - d[u];
	g[u][1] = c[u];
	g[u][0] = 0;
	for(i = 0;i < v[u].size();i++)
	{
		w = v[u][i];
		dfs(w);
		for(j = 1; j<= siz[u];j++)
		{
			h[j] = f[u][j];
		}
		for(j = 1;j <= siz[u];j++)
		{
			for(k = 1;k <= siz[w];k++)
			{
				f[u][j+k] = min(f[u][j+k],h[j]+min(f[w][k],g[w][k]));
			}
			
		}
		for(j = 0; j<= siz[u];j++)
		{
			h[j] = g[u][j];
		}
		for(j = 0;j <= siz[u];j++)
		{
			for(k = 1;k <= siz[w];k++)
			{
				g[u][j+k] = min(g[u][j+k],h[j]+g[w][k]);
			}
			
		}
		siz[u] += siz[w];
	}
	
}
int cyf()
{	
	int i,j,k;
	cin >> n >> b >> c[1] >> d[1];
	//f[1][1] = c[1] - d[1];
	//g[1][1] = c[1];
	for(i = 2;i <= n;i++)
	{
		cin >> c[i] >> d[i] >> x[i];
		v[x[i]].push_back(i);
		//f[i][1] = c[i] - d[i];
		//g[i][1] = c[i];
	}
	dfs(1);
	int ans;
	for(ans = 1;ans <= n;ans++)
	{
		if(min(f[1][ans],g[1][ans]) > b)
			break;
	}
	cout << ans-1 << endl;
	cin.close();	
	cout.close();
	return 0;
}
int hhhh = cyf();
int main() {;}