bzoj 2427 && codevs 1866 tarjian缩点+树形dp

【题意】

2427: [HAOI2010]软件安装

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 929 Solved: 371
[ 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

【解题方法】

观察样例容易知道，这是一堆点套着一个环，由于是有向图，可以缩点，缩点之后就是一个树形dp模板了，缩点不会，还特意去学了一下，可以参考这篇blog：点击打开链接

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int n,m,tot,scc,ind,top;
int v[maxn],w[maxn],sv[maxn],sw[maxn];
int q[maxn],in[maxn*5];bool inq[maxn];
int low[maxn],dfn[maxn],belong[maxn];
int dp[maxn][maxn*5];
int head1[maxn],head2[maxn];
struct edge{
    int to,next;
}e1[maxn*5],e2[maxn*5];
void init1(){
    memset(head1,0,sizeof(head1));
    tot=0;
}
void init2()
{
    memset(head2,0,sizeof(head2));
    tot=0;
}
void addedge1(int u,int v){
    e1[++tot].to=v,e1[tot].next=head1[u],head1[u]=tot;
}
void addedge2(int u,int v){
    in[v]=1;
    e2[++tot].to=v,e2[tot].next=head2[u],head2[u]=tot;
}
void tarjian(int x)
{
    int now=0;
    low[x]=dfn[x]=++ind;
    q[++top]=x;inq[x]=1;
    for(int i=head1[x]; i; i=e1[i].next){
        int v=e1[i].to;
        if(!dfn[v]){
            tarjian(v);
            low[x]=min(low[x],low[v]);
        }else if(inq[v]){
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x]){
        scc++;
        while(now!=x){
            now=q[top--];inq[now]=0;
            belong[now]=scc;
            sv[scc]+=v[now];
            sw[scc]+=w[now];
        }
    }
}
void rebuild(){
    tot=0;
    for(int x=1; x<=n; x++)
    for(int i=head1[x]; i; i=e1[i].next)
        if(belong[e1[i].to]!=belong[x])
            addedge2(belong[x],belong[e1[i].to]);
}
void dfs(int x){
    for(int i=head2[x]; i; i=e2[i].next){
        int v=e2[i].to;
        dfs(v);
        for(int j=m-sw[x]; j>=0; j--){
            for(int k=0; k<=j; k++){
                dp[x][j] = max(dp[x][j],dp[x][k]+dp[v][j-k]);
            }
        }
    }
    for(int j=m; j>=0; j--){
        if(j>=sw[x]) dp[x][j]=dp[x][j-sw[x]]+sv[x];
        else dp[x][j]=0;
    }
}
int main()
{
    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]);
    init1();
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d",&x);
        if(x) addedge1(x,i);
    }
    for(int i=1; i<=n; i++){
        if(!dfn[i]) tarjian(i);
    }
    //init2();
    rebuild();
    for(int i=1; i<=scc; i++){
        if(!in[i]) addedge2(scc+1,i);
    }
    dfs(scc+1);
    cout<<dp[scc+1][m]<<endl;
    return 0;
}