洛谷P2515 [HAOI2010]软件安装（tarjan缩点+树形dp）

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 7 char buf[1<<21],*p1=buf,*p2=buf;
 8 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
 9 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
10 inline int read(){
11     #define num ch-'0'
12     char ch;bool flag=0;int res;
13     while(!isdigit(ch=getc()))
14     (ch=='-')&&(flag=true);
15     for(res=num;isdigit(ch=getc());res=res*10+num);
16     (flag)&&(res=-res);
17     #undef num
18     return res;
19 }
20 const int N=2005;typedef int arr[N];
21 int head[N],Next[N],ver[N],tot;
22 inline void add(int u,int v){
23     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
24 }
25 int hc[N],nc[N],vc[N],tc;
26 inline void addc(int u,int v){
27     vc[++tc]=v,nc[tc]=hc[u],hc[u]=tc;
28 }
29 int n,m,top,cnt,num;arr vis,dfn,low,c,k,st,w,v,d,wc,vv,ins;
30 int dp[N][N];
31 void tarjan(int u){
32     dfn[u]=low[u]=++num,st[++top]=u,vis[u]=1,ins[u]=1;
33     for(int i=head[u];i;i=Next[i]){
34         int v=ver[i];
35         if(!dfn[v]){
36             tarjan(v),cmin(low[u],low[v]);
37         }else if(ins[v]) cmin(low[u],dfn[v]);
38     }
39     if(dfn[u]==low[u]){
40         int y;++cnt;
41         do{
42             y=st[top--],c[y]=cnt,wc[cnt]+=w[y],vv[cnt]+=v[y],ins[y]=0;
43         }while(u!=y);
44     }
45 }
46 void dfs(int u){
47     for(int i=wc[u];i<=m;++i) dp[u][i]=vv[u];
48     for(int i=hc[u];i;i=nc[i]){
49         int v=vc[i];dfs(v);
50         for(int j=m-wc[u];j>=0;--j) for(int q=0;q<=j;++q)
51         cmax(dp[u][j+wc[u]],dp[v][q]+dp[u][j+wc[u]-q]);
52     }
53 }
54 int main(){
55 //    freopen("testdata.in","r",stdin);
56     n=read(),m=read();
57     for(int i=1;i<=n;++i) w[i]=read();
58     for(int i=1;i<=n;++i) v[i]=read();
59     for(int i=1,fa;i<=n;++i)
60     add(fa=read(),i);
61     for(int i=1;i<=n;++i)
62     if(!vis[i]) tarjan(i);
63     for(int u=1;u<=n;++u)
64     for(int i=head[u];i;i=Next[i])
65     if(c[u]!=c[ver[i]]) addc(c[u],c[ver[i]]),++k[c[ver[i]]];
66     for(int i=1;i<=cnt;++i)
67     if(!k[i]) addc(0,i);
68     dfs(0);
69     printf("%d
",dp[0][m]);
70     return 0;
71 }