记录编号	23868	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.202 s
提交时间	2011-03-23 13:28:26	内存使用	2.17 MiB

#include <fstream>
#include <cstdlib>
#include <cstring>

using namespace std;

struct ST_NODE {
	int w, v;
	bool flag;
	ST_NODE *son, *next;
};

int N, M, ct;
int buf[1001][501];
ST_NODE *fl;

int *dp (const ST_NODE *n)
{
	int *f = buf[ct++];

//	memset(f, 0, sizeof(int)*(n->w));
	for (int i=n->w; i<=M; i++)
		f[i] = n->v;

	for (ST_NODE *pi=n->son; pi; pi=pi->next)
	{
		int *g = dp(pi);
		for (int i=M; i>=n->w; i--)
			for (int j=1; j<=M-i; j++)
				if (g[j] + f[i] > f[i+j])
					f[i+j] = g[j] + f[i];
	}

	return f;
}

ST_NODE *ccc (ST_NODE *n, const int sw, const int sv)
{
	if (n == fl  &&  sw)
	{
		ST_NODE *newnode = (ST_NODE*)malloc(sizeof(ST_NODE));
		memset(newnode, 0, sizeof(ST_NODE));
		newnode->v = sv;
		newnode->w = sw;
		return newnode;
	}

	if (n->flag)
		return NULL;

	n->flag = true;
	ST_NODE *ret = NULL, *tmp = NULL;
	for (ST_NODE *pi=n->son; pi; pi=pi->next)
		if ((ret = ccc(pi, sw+n->w, sv+n->v)) != NULL)
		{
			tmp = pi;
			break;
		}

	if (ret)
	{
		ST_NODE *pi = n->son;

		while (pi)
		{
			ST_NODE *pj = pi->next;
			if (pi != tmp)
			{
				pi->next = ret->son;
				ret->son = pi;
			}
			pi = pj;
		}
	}

	return ret;
}

int main ()
{
	ifstream fin("install.in");
	ofstream fout("install.out");

	fin >> N >> M;

	ST_NODE sw[N+1];
	memset(sw, 0, sizeof(sw));

	for (int i=1; i<=N; i++)
		fin >> sw[i].w;
	for (int i=1; i<=N; i++)
		fin >> sw[i].v;
	for (int i=1; i<=N; i++)
	{
		int D;
		fin >> D;
		sw[i].next = sw[D].son;
		sw[D].son = sw + i;
	}

	for (int i=1; i<=N; i++)
		if (!sw[i].flag)
		{
			fl = sw+i;
			ST_NODE *ret = ccc(sw+i, 0, 0);
			if (ret)
			{
				ret->next = sw[0].son;
				sw[0].son = ret;
			}
		}

	int *pi = dp(sw), ans = 0;
	for (int i=0; i<=M; i++)
		if (pi[i] > ans)
			ans = pi[i];

	fout << ans << endl;

	fin.close();
	fout.close();

	return 0;
}