记录编号	211660	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-12-03 09:36:09	内存使用	0.54 MiB

/*好麻烦好麻烦好麻烦QAQ……*/
#include<iostream>
#include<cstdio>
using namespace std;
/*-------------输入函数-------------*/
int n,m,zj1;
int vi[110],wi[110],di[110];
int dito[110],dine[110],dihe[110],sj;//初始图的正向链表，di[]存的逆表 
void init(){
	scanf("%d%d",&n,&m);int i; 
	for(i=1;i<=n;i++)scanf("%d",wi+i);
	for(i=1;i<=n;i++)scanf("%d",vi+i);
	for(i=1;i<=n;i++){
		scanf("%d",di+i);
		if(di[i]){
			dito[++sj]=i,dine[sj]=dihe[di[i]];
			dihe[di[i]]=sj;
		}
	}
}
/*-------------强联通缩点-------------*/
bool flag1[110],flag2[110];
int k,A[110],bh[110],v[110],w[110];//k为集合数,v,w为集合的值 
inline void dfs1(int x){
	flag1[x]=1;
	for(int i=dihe[x];i;i=dine[i])
	if(!flag1[dito[i]])dfs1(dito[i]);
	A[++A[0]]=x;
}
inline void dfs2(int x){
	flag2[x]=1,bh[x]=k;
	w[k]+=wi[x],v[k]+=vi[x];
	if(flag1[di[x]]&&!flag2[di[x]])
	dfs2(di[x]);
}
void con(){
	for(int i=1;i<=n;i++)
	if(!flag1[i]){
		A[0]=0;dfs1(i);
		for(zj1=A[0];zj1;zj1--)
		if(!flag2[A[zj1]]){
			k++;dfs2(A[zj1]);
		}
	}	
}
/*-------------缩点后重建图-------------*/
int to[110],ne[110],he[110];
bool flag[110];
int ri[110],le[110],root;
inline void dfsbu(int x){
	if(!he[x])return;
	le[x]=to[he[x]];
	for(int i=he[x],zj=to[i];i;i=ne[i]){
		dfsbu(to[i]);
		if(zj!=to[i])ri[zj]=to[i],zj=to[i];
	}
}
void rebuild(){
	int i;sj=0;
	for(i=1;i<=n;i++)
	if(di[i]&&bh[di[i]]!=bh[i]){
		to[++sj]=bh[i],ne[sj]=he[bh[di[i]]];
		he[bh[di[i]]]=sj;flag[bh[i]]=1;
	}
	for(i=1;i<=k;i++)if(!flag[i]){root=i;break;}
	for(zj1=root,i=1;i<=k;i++)if(!flag[i]){
		dfsbu(i);
		if(zj1!=i)ri[zj1]=i,zj1=i;
	}
}
/*-------------动规求解-------------*/
int f[110][510],ans[510];
void work(int x,int s){
	if(s<=0)return;int i,j;
	if(ri[x]){
		work(ri[x],s);
		if(!le[x]){
			for(i=1;i<w[x];i++)f[x][i]=f[ri[x]][i];
			for(;i<=s;i++)
			f[x][i]=max(f[ri[x]][i],f[ri[x]][i-w[x]]+v[x]);
			return;
		}
	}
	if(le[x]){
		work(le[x],s-w[x]);
		if(!ri[x]){
			for(i=w[x];i<=s;i++)
			f[x][i]=v[x]+f[le[x]][i-w[x]];
			return;
		}
	}
	for(i=1;i<=s;i++)f[x][i]=f[ri[x]][i];
	for(i=w[x];i<=s;i++)for(j=w[x];j<=i;j++){//给左子树 
		zj1=f[le[x]][j-w[x]]+v[x]+f[ri[x]][i-j];
		if(f[x][i]<zj1)f[x][i]=zj1;
	}
}
/*-------------主函数-------------*/
int main(){
//	freopen("a.txt","r",stdin);
	freopen("install.in","r",stdin);
	freopen("install.out","w",stdout);
	init();
	con();
	rebuild();
	work(root,m);
	printf("%d\n",f[root][m]);
	return 0;
}