bzoj2427

tarjan+dp

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<ctime>
 5 #include<cmath>
 6 #include<iostream>
 7 #include<algorithm>
 8 #include<stack>
 9 #define clr(a,x) memset(a,x,sizeof(x))
10 #define rep(i,l,r) for(int i=l;i<r;i++)
11 using namespace std;
12 typedef long long ll;
13 const int maxn=109,maxm=509;
14 int dfn=0,cnt=1,scccnt=0,n,m,w[maxn],v[maxn],W[maxn],V[maxn],scc[maxn],low[maxn],pre[maxn],f[maxn],to[maxn];
15 int root,d[maxn][maxm],Cnt[maxn],son[maxn][maxn];
16 bool p[maxn];
17 stack<int>S;
18 void tarjan(int x){
19     low[x]=pre[x]=++dfn;
20     S.push(x);
21     if(f[x]){
22         if(!pre[f[x]]){
23             tarjan(f[x]);
24             low[x]=min(low[x],low[f[x]]);
25         }else if(!scc[f[x]]) low[x]=min(low[x],pre[f[x]]);
26     }
27     if(pre[x]==low[x]){
28         int k=0;++scccnt;
29         while(k!=x){
30             k=S.top();S.pop();
31             scc[k]=scccnt;
32             W[scccnt]+=w[k];
33             V[scccnt]+=v[k];
34         }
35     }
36 }
37 void dp(int x){
38     rep(i,V[x],m+1) d[x][i]=W[x];
39     rep(i,0,Cnt[x]){
40         dp(son[x][i]);
41         for(int h=m;h>=V[x];h--)
42             rep(t,0,h-V[x]+1) 
43                 d[x][h]=max(d[x][h],d[x][h-t]+d[son[x][i]][t]);
44     }
45 }
46 int main(){
47     scanf("%d%d",&n,&m);
48     rep(i,1,n+1) scanf("%d",v+i);
49     rep(i,1,n+1) scanf("%d",w+i);
50     rep(i,1,n+1) scanf("%d",f+i);
51     rep(i,1,n+1) if(!scc[i]) tarjan(i);
52     clr(p,0);
53     rep(i,1,n+1){
54         if(f[i]&&scc[i]!=scc[f[i]]){
55             p[scc[i]]=1;
56             to[scc[i]]=scc[f[i]];
57             son[scc[f[i]]][Cnt[scc[f[i]]]++]=scc[i];
58         }
59     }
60     root=scccnt+1;
61     rep(i,1,scccnt+1) if(!p[i]){
62         son[root][Cnt[root]++]=i;
63         to[i]=root;
64     }
65     dp(root);
66     cout<<*max_element(d[root],d[root]+m+1)<<"
";
67     return 0;
68 }

View Code

2427: [HAOI2010]软件安装

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

HINT

Source

Day2

[Submit][Status][Discuss]