记录编号	57091	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.084 s
提交时间	2013-04-06 08:25:29	内存使用	0.79 MiB

#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int SIZEN=222,SIZEM=555;
//节点下标是1~n
int n,m;//n是软件个数,m是磁盘容量
int w[SIZEN]={0},v[SIZEN]={0};//花费和价值
int d[SIZEN]={0};
deque<int> c[SIZEN];//每棵树的邻接表
int sumcir=0;
bool visit[SIZEN]={0};//缩点中是否被访问到
void loop(int x){//有递归写法,但是不对称(强迫症...)
	//如果有环,就把环上所有点连到一个新点上
	deque<int> st;
	bool instack[SIZEN]={0};
	int temp=x,start;
	bool flag=false;
	while(1){
		st.push_back(temp);
		visit[temp]=instack[temp]=true;
		temp=d[temp];
		if(temp==0) break;
		if(instack[temp]){
			flag=true;
			start=temp;
			break;
		}
		if(visit[temp]) break;
	}
	if(flag){//找到了一个环
		sumcir++;
		w[n+sumcir]=v[n+sumcir]=d[n+sumcir]=0;
		int i=st.size()-1;
		while(1){
			d[st[i]]=n+sumcir;
			w[n+sumcir]+=w[st[i]],v[n+sumcir]+=v[st[i]];
			w[st[i]]=v[st[i]]=0;
			if(st[i]==start) break;
			i--;
		}
	}
}
void contract(void){//缩点
	int i;
	for(i=1;i<=n;i++){
		if(!visit[i]) loop(i);
	}
	n+=sumcir+1;//最后加上一个"超级根"
	v[n]=w[n]=d[n]=0;
	for(i=1;i<n;i++){
		if(!d[i]){//某棵树的根
			d[i]=n;
		}
	}
	for(i=1;i<=n;i++){
		if(d[i]) c[d[i]].push_back(i);
	}
}
int f[SIZEN][SIZEM]={0};//f[i][j]表示以i为根的泛化物品用空间j的最大价值
void dp(int x){
	if(!c[x].size()){//叶子节点
		f[x][w[x]]=v[x];
		return;
	}
	int i,j,k,temp1,temp2;
	for(i=0;i<(int)c[x].size();i++) dp(c[x][i]);
	int now[SIZEM]={0};
	for(i=c[x].size()-1;i>=1;i--){
		temp1=c[x][i],temp2=c[x][i-1];//当前考虑的两个点,要往temp2处合并
		for(j=1;j<=m;j++){
			now[j]=0;
			for(k=0;k<=j;k++){
				now[j]=max(now[j],f[temp1][k]+f[temp2][j-k]);
			}
		}
		for(j=1;j<=m;j++) f[temp2][j]=now[j];
	}
	for(i=1;i<=m;i++) f[x][i]=f[c[x][0]][i];
	for(i=m;i>=w[x];i--) f[x][i]=f[x][i-w[x]]+v[x];
	for(i=w[x]-1;i>=0;i--) f[x][i]=0;
}
void read(void){
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&w[i]);
	for(i=1;i<=n;i++) scanf("%d",&v[i]);
	for(i=1;i<=n;i++){
		scanf("%d",&d[i]);
	}
}
int main(){
	freopen("install.in","r",stdin);
	freopen("install.out","w",stdout);
	read();
	contract();
	dp(n);
	int ans=0,i;
	for(i=1;i<=m;i++) if(f[n][i]>ans) ans=f[n][i];
	printf("%d\n",ans);
	return 0;
}