題目描述

現在我們的手頭有N個軟件，對于一個軟件i，它要占用Wi的磁盤空間，它的價值為Vi。我們希望從中選擇一些軟件安裝到一臺磁盤容量為M計算機上，使得這些軟件的價值盡可能大（即Vi的和最大）。

但是現在有個問題：軟件之間存在依賴關系，即軟件i只有在安裝了軟件j（包括軟件j的直接或間接依賴）的情況下才能正確工作（軟件i依賴軟件j)。幸運的是，一個軟件最多依賴另外一個軟件。如果一個軟件不能正常工作，那么它能夠發揮的作用為0。

我們現在知道了軟件之間的依賴關系：軟件i依賴軟件Di。現在請你設計出一種方案，安裝價值盡量大的軟件。一個軟件只能被安裝一次，如果一個軟件沒有依賴則Di=0，這時只要這個軟件安裝了，它就能正常工作。

輸入輸出格式

輸入格式：

?

第1行：N, M （0<=N<=100, 0<=M<=500）

第2行：W1, W2, ... Wi, ..., Wn （0<=Wi<=M ）

第3行：V1, V2, ..., Vi, ..., Vn （0<=Vi<=1000 ）

第4行：D1, D2, ..., Di, ..., Dn （0<=Di<=N, Di≠i ）

?

輸出格式：

?

一個整數，代表最大價值

?

輸入輸出樣例

輸入樣例#1：
3 10 5 5 6 2 3 4 0 1 1 輸出樣例#1：
5

?

題解

• 首先，一個軟件只能依賴一個軟件，那么我們將被依賴的軟件向依賴它的軟件上連一條邊，這么發現，每個點的入度為1
• 每個點入度為1的圖是什么，那就是樹，但是這棵樹有可能會形成環，然后就要打tarjan縮環
• 設f[i][j]為以i根的樹，容量為j的最大價值（不處理根），那么答案就是f[0][m]
• 狀態轉移方程就很顯然了，類似于在樹上做一個背包，取一個點的前提條件是它的根被取了
• f[i][j]=max(f[i][j],f[i?k][j]+f[son][k?w[son]]+v[son])（k為枚舉的一個容量）

代碼

1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 struct edge { int to,from; }e[110]; 5 int n,m,cnt,tot,k,w[110],v[110],head[110],low[110],dfn[110],vis[110],sta[110],bel[110],w1[110],v1[110],s[110],g[110][110],f[110][510]; 6 void insert(int x,int y) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; } 7 void tarjan(int x) 8 { 9 dfn[x]=low[x]=++dfn[0],sta[++sta[0]]=x,vis[x]=1; 10 for (int i=head[x];i;i=e[i].from) 11 if (!dfn[e[i].to]) 12 { 13 tarjan(e[i].to); 14 low[x]=min(low[x],low[e[i].to]); 15 } 16 else if (vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); 17 if (dfn[x]==low[x]) 18 { 19 tot++; 20 do 21 { 22 k=sta[sta[0]--],vis[k]=0; 23 bel[k]=tot,w1[tot]+=w[k],v1[tot]+=v[k]; 24 } 25 while (k!=x); 26 } 27 } 28 void dfs(int x) 29 { 30 for (int i=1;i<=tot;i++) 31 if (g[x][i]) 32 { 33 dfs(i); 34 for (int j=m;j>=w1[i];j--) for (int k=w1[i];k<=j;k++) f[x][j]=max(f[x][j],f[i][k-w1[i]]+v1[i]+f[x][j-k]); 35 } 36 } 37 int main() 38 { 39 scanf("%d%d",&n,&m); 40 for (int i=1;i<=n;i++) scanf("%d",&w[i]); 41 for (int i=1;i<=n;i++) scanf("%d",&v[i]); 42 for (int i=1,x;i<=n;i++) 43 { 44 scanf("%d",&x); 45 if (x) insert(x,i); 46 } 47 for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); 48 for (int i=1;i<=n;i++) 49 for (int j=head[i];j;j=e[j].from) 50 if (bel[i]!=bel[e[j].to]&&!g[bel[i]][bel[e[j].to]]) 51 g[bel[i]][bel[e[j].to]]=1,s[bel[e[j].to]]++; 52 for (int i=1;i<=n;i++) if (!s[i]) g[0][i]=1; 53 dfs(0); 54 printf("%d",f[0][m]); 55 }

?

轉載于:https://www.cnblogs.com/Comfortable/p/9833241.html

總結

以上是生活随笔為你收集整理的[tarjan][树形dp] 洛谷 P2515 软件安装的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。