P2515: Software Installation [HAOI2010]

Problem Description: You have computer with M amount of storage. There are N softwares you are going to install on the computer. The ith computer takes #include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1005; int N,M; struct software{ int val,space,dep; software(int a = 0,int b = 0,int c = 0):val(a),space(b),dep(c){}; } a[maxn],b[maxn]; int deg[maxn],f[maxn][maxn],dfn[maxn],low[maxn],group[maxn],gp_cnt; stack<int> S; vector<int> G1[maxn],G2[maxn]; queue<int> q; void addedge1(int u,int v){ G1[u].push_back(v); } void addedge2(int u,int v){ G2[u].push_back(v); } int dfs_clock; void tarjan(int u){ dfn[u] = low[u] = ++dfs_clock; S.push(u); for(int i = 0; i < G1[u].size(); i++){ int v = G1[u][i]; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); } else if(!group[v]){ low[u] = min(low[u],dfn[v]); } } if(low[u] == dfn[u]){ gp_cnt++; for(;;){ int x = S.top(); S.pop(); group[x] = gp_cnt; if(x == u) break; } } } void dfs(int u){ for(int i = b[u].space; i <= M; i++) f[u][i] = b[u].val; for(int i = 0; i < G2[u].size(); i++){ int v = G2[u][i]; dfs(v); for(int j = M - b[u].space; j >= 0; j--){ for(int k = 0; k <= j; k++){ f[u][j + b[u].space] = max(f[u][j + b[u].space],f[u][j + b[u].space - k] + f[v][k]); } } } } int main(){ FAST_IO cin>>N>>M; for(int i = 1; i <= N; i++) cin>>a[i].space; for(int i = 1; i <= N; i++) cin>>a[i].val; for(int i = 1; i <= N; i++) {cin>>a[i].dep; if(a[i].dep) addedge1(a[i].dep,i);}; for(int i = 1; i <= N; i++){ if(!group[i]) tarjan(i); } for(int i = 1; i <= N; i++){ b[group[i]].space += a[i].space; b[group[i]].val += a[i].val; } for(int i = 1; i <= N; i++){ if(a[i].dep && group[a[i].dep] != group[i]){ deg[group[i]]++; addedge2(group[a[i].dep],group[i]); } } for(int i = 1; i <= N; i++){ if(!deg[group[i]]){ addedge2(gp_cnt + 1,group[i]); } } dfs(gp_cnt + 1); int ans = 0; for(int i = 0; i <= M; i++) ans = max(ans,f[gp_cnt + 1][i]); cout<<ans<<endl; return 0; }

 

Leave a Reply

Your email address will not be published. Required fields are marked *