BZOJ 2427 HAOI2010 软件安装

2427: [HAOI2010]软件安装

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1855 Solved: 730
[Submit][Status][Discuss]

Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）
      第2行：W₁, W₂, ... W_i, ..., W_n （0<=W_i<=M ）
      第3行：V₁, V₂, ..., V_i, ..., V_n  （0<=Vi<=1000 ）
      第4行：D₁, D₂, ..., D_i, ..., D_n（0<=D_i<=N, D_i≠i ）

Output

一个整数，代表最大价值。

Sample Input

3 10
5 5 6
2 3 4
0 1 1

Sample Output

HINT

Source

Day2

思路很显然首先tarjin缩一下点，然后dp即可

f[i][j]表示以i节点为根共用就j的储存空间，所获的最大获利，注意做背包的转移边界

我这个SB查了一下午就是因为边界没限制，多转移了好多

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN=1e3+10;
struct node{
    int y,next,x;
}e[MAXN],E[MAXN];
int linkk[MAXN],len=0,n,m,a[MAXN],b[MAXN],tot=0,stark[MAXN],top=0,dfn[MAXN],Len=0,Linkk[MAXN],ine[MAXN],vis[MAXN],w[MAXN],v[MAXN],low[MAXN],dfs_clock=0,f[MAXN][MAXN];
inline void insert(int xx,int yy){
    e[++len].y=yy;e[len].next=linkk[xx];e[len].x=xx;linkk[xx]=len;
}
inline void insertt(int xx,int yy){
    E[++Len].y=yy;E[Len].next=Linkk[xx];Linkk[xx]=Len;
}
inline void tarjin(int st){
    dfn[st]=low[st]=++dfs_clock;
    vis[st]=1;stark[++top]=st;
    for(int i=linkk[st];i;i=e[i].next){
        if(!dfn[e[i].y]){
            tarjin(e[i].y);
            low[st]=min(low[e[i].y],low[st]);
        }
        else if(vis[e[i].y]) low[st]=min(low[st],dfn[e[i].y]); 
    }
    if(dfn[st]==low[st]){
        tot++;
        int k;
        do{
            k=stark[top--];
            w[tot]+=a[k];
            v[tot]+=b[k];
            vis[k]=0;
            ine[k]=tot;
        }while(k!=st);
    }
}
void init(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i++){
       b[i]=read();
    }
    for(int i=1;i<=n;i++){
        int xx=read();
        insert(xx,i);
    }
    for(int i=1;i<=n;i++){
        if(!ine[i]) tarjin(i);
    }
}
int cnt[MAXN]={};
inline void rebuild(){
    for(int i=1;i<=len;i++){
        int xx=ine[e[i].x];
        int yy=ine[e[i].y];
        if(xx!=yy) insertt(xx,yy),cnt[yy]++;
        
    }
    for(int i=1;i<=tot;i++){
        if(!cnt[i]) insertt(0,i);
    }
}
inline int dp(int st){
    //cout<<st<<endl;
    vis[st]=1;
    for(int i=w[st];i<=m;i++){
        f[st][i]=v[st];
    }
    for(int i=Linkk[st];i;i=E[i].next){
        if(vis[E[i].y]) continue;
        dp(E[i].y);
        for(int j=m;j>=w[st];j--){
            for(int k=1;k<=j-w[st];k++){
                f[st][j]=max(f[st][j],f[st][j-k]+f[E[i].y][k]);
            }
        }
    }
}
void solve(){
    rebuild();
    memset(vis,0,sizeof(vis));
    dp(0);
    int minn=-10000;
    for(int i=1;i<=m;i++){
        minn=max(minn,f[0][i]);
    }
    cout<<minn<<endl;
}
int main(){
    init();
    solve();
    return 0;
}