【BZOJ-2427】軟件安裝 Tarjan + 樹形01背包

2427: [HAOI2010]軟件安裝

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?960??Solved:?380
[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

5

HINT

Source

Day2

Solution

把環縮成一個點...

建立超級根0....

然后樹形01背包

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f;
}
#define MAXN 110
#define MAXM 510
struct EdgeNode{int next,to;}edge[MAXN<<1],road[MAXN<<1];
int head[MAXN],cnt=1,first[MAXN],tot=1;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {if (!u) return; AddEdge(u,v);}
int w[MAXN],v[MAXN],V[MAXN],W[MAXN],N,M;
int dfn[MAXN],low[MAXN],st[MAXN],top,visit[MAXN],belong[MAXN],size[MAXN],dfsn,scc;
inline void Tarjan(int x)
{dfn[x]=low[x]=++dfsn; visit[x]=1; st[++top]=x;for (int i=head[x]; i; i=edge[i].next)if (!dfn[edge[i].to]) Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);else if (visit[edge[i].to]) low[x]=min(dfn[edge[i].to],low[x]);if (dfn[x]==low[x]){int stp=0;scc++;while (x!=stp) stp=st[top--],size[scc]++,W[scc]+=w[stp],V[scc]+=v[stp],belong[stp]=scc,visit[stp]=0;}
}
inline void AddRoad(int u,int v) {tot++; road[tot].next=first[u]; first[u]=tot; road[tot].to=v;}
inline void InsertRoad(int u,int v) {AddRoad(u,v); AddRoad(v,u);}
bool flag[MAXN];
inline void Rebuild()
{for (int i=1; i<=N; i++)for (int j=head[i]; j; j=edge[j].next)if (belong[i]!=belong[edge[j].to])InsertRoad(belong[i],belong[edge[j].to]),flag[belong[edge[j].to]]=1;for (int i=1; i<=scc; i++) if (!flag[i]) InsertRoad(0,i);
}
int f[MAXN][MAXM],g[MAXN][MAXM];
void DP(int x,int last)
{    for (int i=first[x]; i; i=road[i].next)if (road[i].to!=last){DP(road[i].to,x);for (int j=M-W[x]; j>=0; j--)for (int k=0; k<j; k++)g[x][j]=max(g[x][j],g[x][k]+f[road[i].to][j-k]);}for (int i=0; i<=M-W[x]; i++) f[x][i+W[x]]=g[x][i]+V[x];
}
int main()
{N=read(),M=read();for (int i=1; i<=N; i++) w[i]=read();for (int i=1; i<=N; i++) v[i]=read();for (int f,i=1; i<=N; i++) f=read(),InsertEdge(f,i);for (int i=1; i<=N; i++) if (!dfn[i]) Tarjan(i);Rebuild();DP(0,0);printf("%d\n",f[0][M]);return 0;
}

?