记录编号	232141	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2016-02-28 18:28:42	内存使用	5.43 MiB

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int e=505;
int n,m,tmpw=0,tmpn;
int w[e]={0},v[e]={0},b[e]={0},c[e]={0},f[e][5*e]={0},d[e]={0};
bool mapp[e][e]={0};
void floride()
{
    for(int i=1;i<=n;i++)//弗洛里德判断是否有环；
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(mapp[k][i]==1 && mapp[i][j]==1)
                    mapp[k][j]=1;
}
void merge()//合点
{
    tmpn=n;
    for(int i=1;i<=tmpn;i++)
        for(int j=1;j<=tmpn;j++)
        {
            if(mapp[i][j]==1 && mapp[j][i]==1 && i!=j && w[i]>0 && w[j]>0)//如果是新环；
            {
                tmpn++;
                v[tmpn]=v[i]+v[j];
                w[tmpn]=w[i]+w[j];
                tmpw--;    w[i]=tmpw;    w[j]=tmpw;    //tmpw+tmpn永远等于最开始的n
            }
            
            //如果j依赖的点被合并(是旧环),且j在环里
            if(w[d[j]]<0 && w[j]>0 && mapp[j][d[j]]==1 && mapp[j][d[j]]==1)    
            {
                w[n-w[d[j]]]+=w[j];
                v[n-w[d[j]]]+=v[j];
                w[j]=w[d[j]];
            }          
            //如果j依赖的点在环里，但是j不在环里
            if(w[d[j]]<0 && w[j]>0)
                if((mapp[j][d[j]]==1 && mapp[d[j]][j]==0) || (mapp[j][d[j]]==0 && mapp[d[j]][j]==1))
                    d[j]=n-w[d[j]];
        }
}
int  dfs(int x,int k)
{
    if(f[x][k]>0)    return(f[x][k]);
    if(x==0 || k<=0)    return(0);
    //不取x
    f[b[x]][k]=dfs(b[x],k);
    f[x][k]=f[b[x]][k];
        int y=k-w[x];
        for(int i=0;i<=y;i++)
        {
            f[c[x]][y-i]=dfs(c[x],y-i);
            f[b[x]][i]=dfs(b[x],i);
            f[x][k]=max(f[x][k],v[x]+f[c[x]][y-i]+f[b[x]][i]);
        }
    return(f[x][k]);
}
int main()
{
    freopen("install.in","r",stdin);
    freopen("install.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        d[i]=a;
        mapp[a][i]=1;
    }
    floride();
    merge();
    
    //多叉转二叉
    for(int i=1;i<=tmpn;i++)
        if(w[i]>0)
        {
            b[i]=c[d[i]];
            c[d[i]]=i;
        }
    cout<<dfs(c[0],m);
    return 0;
}
//BY 魔术羊