BZOJ 2427 /HAOI 2010 軟體安裝 tarjan縮點+樹形DP

終于是道中文題了。。。。

當時考試的時候就考的這道題。。。。 果斷GG。

思路：

因為有可能存在依賴環，是以呢 先要tarjan一遍 來縮點。

随後就進行一遍樹形DP就好了。。

x表示目前的節點。j表示j的空間最多能放多少價值的軟體。

狀态轉移方程：f[x][j]=max(f[x][j],f[x.son][k]+f[x][j-k])

題目說：軟體i隻有在安裝了軟體j（包括軟體j的直接或間接依賴）的情況下才能正确工作

這句話怎麼翻譯呢？ 直接把W[i]以下的價值設為負無窮不就好了嘛。。

// by SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,xx,t=0,tot=0,cnt=0,top=0,maxx=0,low[105],dfn[105],s[105],p[105],D[105],f[505][505];
int first[105],next[105],v[105],W[105],WW[105],V[105],VV[105],vis[105],in[105];
void add(int x,int y){v[tot]=y,next[tot]=first[x];first[x]=tot++;}
void tarjan(int x){
    low[x]=dfn[x]=++cnt;vis[x]=1;s[++top]=x;
    for(int i=first[x];~i;i=next[i])
        if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);
        else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);
    if(low[x]==dfn[x]){t++;do xx=s[top--],vis[xx]=0,p[xx]=t,WW[t]+=W[xx],VV[t]+=V[xx];while(xx!=x);}
}
void dfs(int x){
    for(int i=first[x];~i;i=next[i]){
        dfs(v[i]);
        for(int j=m;j>=0;j--)
            for(int k=j;k>=0;k--)
                f[x][j]=max(f[x][j],f[v[i]][k]+f[x][j-k]);
    }
}
int main(){
    memset(first,-1,sizeof(first));
    memset(f,0xcf,sizeof(f));
    scanf("%d%d",&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++)scanf("%d",&D[i]),add(D[i],i);
    for(int i=0;i<=n;i++)if(!dfn[i])tarjan(i);
    memset(first,-1,sizeof(first));
    for(int i=1;i<=n;i++)if(p[D[i]]!=p[i])add(p[D[i]],p[i]),in[p[i]]++;
    for(int i=1;i<=t;i++)if(!in[i]&&i!=p[0])add(p[0],i);
    for(int i=1;i<=t;i++)for(int j=WW[i];j<=m;j++)f[i][j]=VV[i];
    dfs(p[0]);
    printf("%d\n",f[p[0]][m]);
}