记录编号	289487	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	Respawn	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2016-08-04 21:23:48	内存使用	0.58 MiB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
const int maxn=110;
struct Edge
{
	int to,next,from;
}e[maxn];
struct Tree
{
	int lch,rch;
}a[maxn];
int so1[maxn],so2[maxn][maxn],n,m,jia[maxn],zho[maxn],len,head[maxn],l[maxn],Fi[maxn],tim;
int num,b[maxn],ff[maxn][510],du[maxn];
int Z[maxn],J[maxn];
stack <int> q;
bool flag[maxn],flag2[maxn];
void Dfs(int);
void Insert(int,int);
void Insert2(int,int);
int dg(int,int);
int main()
{
	freopen("install.in","r",stdin);
	freopen("install.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&zho[i]);
	for(int i=1;i<=n;i++)scanf("%d",&jia[i]);
	for(int i=1;i<=n;i++)
	{
		int x;scanf("%d",&x);
		if(x==0)continue;
		Insert(x,i);
	}
	for(int i=1;i<=n;i++) if(!Fi[i]) Dfs(i);
	for(int i=1;i<=len;i++){
		int x=e[i].from,y=e[i].to;
		int xx=b[x],yy=b[y];
		if(xx==yy) continue;
		Insert2(xx,yy); du[yy]++;
	}
	for(int i=1;i<=num;i++) if(!du[i]) Insert2(num+1,i);
	int ans=dg(num+1,m);printf("%d",ans);
	return 0;
}
void Insert2(int x,int y)
{
	if(a[x].lch==0)a[x].lch=y;
	else
	{
		int t=a[x].lch;
		while(a[t].rch!=0)
		{
			t=a[t].rch;
		}
		a[t].rch=y;
	}
}
void Insert(int x,int y)
{
	len++;e[len].to=y;e[len].next=head[x];e[len].from=x;
	head[x]=len;
}
void Dfs(int x)
{
	flag[x]=1;tim++;Fi[x]=tim;l[x]=tim;q.push(x);
	for(int i=head[x];i!=-1;i=e[i].next)
	{
		int j=e[i].to;
		if(Fi[j]==0)Dfs(j),l[x]=min(l[x],l[j]);
		else if(flag[j]==1)l[x]=min(l[x],Fi[j]);
	}
	if(l[x]==Fi[x])
	{
		num++;
		int k=0x7f7f7f7f;
		while(k!=x){
			k=q.top(),q.pop(),b[k]=num,flag[k]=0;
			Z[num]+=zho[k]; J[num]+=jia[k];
		}
	}
}
int dg(int x,int y)
{
	if(x==0||y<=0)return 0;
	if(ff[x][y])return ff[x][y];
	ff[x][y]=dg(a[x].rch,y);
	for(int i=Z[x];i<=y;i++)
	{
		ff[x][y]=max(ff[x][y],J[x]+dg(a[x].lch,i-Z[x])+dg(a[x].rch,y-i));
	}
	return ff[x][y];
}