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

題解

比較裸的樹上背包...只不過可能成環比較坑。

$tarjan$縮點之后再全部連向一個虛點，直接樹形$DP$。

1 //It is made by Awson on 2017.11.5 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <string> 10 #include <cstdio> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Min(a, b) ((a) < (b) ? (a) : (b)) 17 #define Max(a, b) ((a) > (b) ? (a) : (b)) 18 #define Abs(x) ((x) < 0 ? (-(x)) : (x)) 19 using namespace std; 20 const int N = 100; 21 const int M = 500; 22 23 int n, m; 24 int W[N+5], V[N+5], w[N+5], v[N+5], d[N+5]; 25 struct tt { 26 int to, next; 27 }edge[N+5]; 28 int path[N+5], top; 29 int dfn[N+5], low[N+5], cnt_time; 30 stack<int>S; 31 bool vis[N+5], in[N+5]; 32 int sccno[N+5], sccnum; 33 int f[N+5][M+5]; 34 35 void tarjan(int x) { 36 dfn[x] = low[x] = ++cnt_time; S.push(x); vis[x] = 1; 37 for (int i = path[x]; i; i = edge[i].next) { 38 if (vis[edge[i].to]) low[x] = Min(low[x], dfn[edge[i].to]); 39 else if (!dfn[edge[i].to]) { 40 tarjan(edge[i].to); low[x] = Min(low[x], low[edge[i].to]); 41 } 42 } 43 if (dfn[x] == low[x]) { 44 sccnum++; int u = -1; 45 do { 46 u = S.top(); S.pop(); 47 vis[u] = 0, sccno[u] = sccnum; 48 w[sccnum] += W[u], v[sccnum] += V[u]; 49 }while (u != x); 50 } 51 } 52 void dfs(int u) { 53 for (int i = path[u]; i; i = edge[i].next) { 54 dfs(edge[i].to); 55 for (int j = m; j >= 0; j--) 56 for (int k = 0; k <= j; k++) 57 f[u][j] = Max(f[u][k]+f[edge[i].to][j-k], f[u][j]); 58 } 59 for (int i = m; i >= 0; i--) { 60 if (i-w[u] >= 0) f[u][i] = f[u][i-w[u]]+v[u]; 61 else f[u][i] = 0; 62 } 63 } 64 void add(int u, int v) { 65 edge[++top].to = v; 66 edge[top].next = path[u]; 67 path[u] = top; 68 } 69 void work() { 70 scanf("%d%d", &n, &m); 71 for (int i = 1; i <= n; i++) scanf("%d", &W[i]); 72 for (int i = 1; i <= n; i++) scanf("%d", &V[i]); 73 for (int i = 1; i <= n; i++) { 74 scanf("%d", &d[i]); add(d[i], i); 75 } 76 for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); 77 memset(path, 0, sizeof(path)); top = 0; 78 for (int i = 1; i <= n; i++) if (sccno[i] != sccno[d[i]]) add(sccno[d[i]], sccno[i]), in[sccno[i]] = 1; 79 for (int i = 1; i <= sccnum; i++) if (!in[i]) add(0, i); 80 dfs(0); 81 int ans = 0; 82 for (int i = 0; i <= m; i++) ans = Max(f[0][i], ans); 83 printf("%d", ans); 84 } 85 int main() { 86 work(); 87 return 0; 88 }

?

轉載于:https://www.cnblogs.com/NaVi-Awson/p/7787004.html

總結

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

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