bzoj 2427 软件安装

题目描述

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

输入

第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 ）

输出

一个整数，代表最大价值。

样例输入

3 10
5 5 6
2 3 4
0 1 1

样例输出

来源

Day2

（转自http://www.lydsy.com/JudgeOnline/problem.php?id=2427）

　　这道题看起来像是树归，首先来判断一下，一个软件只能依赖于一个软件，正如树，一个节点只有一个父节点（除了根节点）（把所有节点都连接到0号节点下），但是来构思一组数据:

　　D： 2 3 1

　　像这样，1依赖于2，2依赖于3.，3依赖于1，构成了一个环（强连通分量），明显不符合树的性质，但是仔细想想，要么全选要么全不选

就可以把它当成一个节点来看待。

　　至于缩点。。。这个也比较简单，和codevs上"爱在心中"差不多，首先给belong数组赋初值：

for(int i = 0;i <= n;i++)
belong[i] = i;

　　再Tarjan一次，将元素弹出栈时要将对应belong数组中这个强连通分量的值全部设成这中间任意元素的值（但必须一样）

接着for循环扫描一次，凡是belong[i] != i的像这样处理一下:

w[belong[i]] += w[i];
v[belong[i]] += v[i];

　　如果出现访问d[i]就像这样访问:

d[belong[i]]......

　　是不是十分方便快捷？（除了Tarjan算法的代码复杂度）

　　下面思考一下树归方程，感觉如果玩多叉树的话状态很多，就转成二叉树，为了代码简洁，有这么两种方法

第一种方法是记录每个节点添加进的"兄弟"的地址，就加一个指针变量，添加一个"儿子"或者"兄弟"时,就访问

这个对应的指针变量，先正常加入，然后把指针指向它

for(int i = 1;i <= n;i++){
    for(int j = head[i];j;j = edge[j].next){
        if(belong[i] == i && belong[i] != belong[edge[j].end]){
            if(node[i]->left != NULL)
                node[i]->left->bro = &node[edge[belong[j]].end];
            else node[i]->left = &node[edge[belong[j]].end];;
        }
    }
}

　　是不是显得有点麻烦？而且严重牺牲了可读性，在看了某大神的代码后，我知道了这种方法:

用bro[i]储存i节点的右子树(原先的"兄弟"),用son[i]储存i节点的左子树(原先的"子节点")，

然后：

最后：

代码实现也比较简单：

for(int i = 1;i <= n;i++){
    for(int j = head[i];j;j = edge[j].next){
        if(belong[i] == i && belong[i] != belong[edge[j].end]){
            bro[i] = son[belong[edge[j].end]];
            son[belong[edge[j].end]] = i;
        }
    }
}

　　另外关于左右子树出现空的时候，如果多加几个if语句的话，可能树形DP的代码就和Tarjan算法有的一拼了，可以把

它的左右子树的位置设成一个值为0的节点，这就相当于一个空节点，但并不影响计算结果

　　写出树归方程:

f[index][i] = max(f[index][i],v[index] + f[left][j] + f[right][limit - j]);

（index是第index个节点，limit是i - w[i],left = son[index],right = bro[index]）

最后附上我超级不简洁的代码（如果想要速度更快，可以把cin，cout改成scanf和printf）

Code:

  1 /**
  2  * bzoj
  3  * Problem#2427
  4  * Accepted
  5  * Time:220ms
  6  * Memory:1492k
  7  */
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<stack>
 12 #include<vector>
 13 #define _min(a,b) ((a)<(b))?(a):(b)
 14 using namespace std;
 15 typedef bool boolean;
 16 typedef class Edge{
 17     public:
 18         int end;
 19         int next;
 20         Edge():end(0),next(0){}
 21         Edge(int end,int next):end(end),next(next){}
 22 }Edge;
 23 Edge *edge;
 24 int n,m;
 25 int *w;        //软件大小
 26 int *v;        //价值 
 27 int *d;
 28 int *head;
 29 int top;
 30 inline void addEdge(int from,int end){
 31     top++;
 32     edge[top].next=head[from];
 33     edge[top].end=end;
 34     head[from]=top;
 35 }
 36 boolean *visited;
 37 int *visitID;
 38 int *exitID;
 39 int entryed;
 40 stack<int> sta;
 41 int *belong;
 42 boolean *inStack;
 43 int *bro;
 44 int *son;
 45 void getSonMap(int end){
 46     int now=-1;
 47     int exits=0;
 48     while(now!=end){
 49         now=sta.top();
 50         belong[now]=end;
 51         inStack[now]=false;
 52         exits++;
 53         sta.pop();
 54     }
 55 }
 56 void Tarjan(const int pi){
 57     int index=head[pi];
 58     visitID[pi]=++entryed;
 59     exitID[pi]=visitID[pi];
 60     visited[pi]=true;
 61     inStack[pi]=true;
 62     sta.push(pi);
 63     while(index!=0){
 64         if(!visited[edge[index].end]){
 65             Tarjan(edge[index].end);
 66             exitID[pi]=_min(exitID[pi],exitID[edge[index].end]);
 67         }else if(inStack[edge[index].end]){
 68             exitID[pi]=_min(exitID[pi],visitID[edge[index].end]);
 69         }
 70         index=edge[index].next;
 71     }
 72     if(exitID[pi]==visitID[pi]){
 73         getSonMap(pi);
 74     }
 75 }
 76 void rebuild(){
 77     vector<int> indexs;
 78     for(int i=1;i<=n;i++){
 79         if(belong[i] != i){
 80             v[belong[i]] += v[i];
 81             w[belong[i]] += w[i];
 82             indexs.push_back(belong[i]);
 83         }
 84     }
 85     for(int i = 0;i < indexs.size();i++)
 86         edge[head[indexs[i]]].end = 0;
 87 }
 88 void create(){
 89     bro = new int[(const int)(n + 1)];
 90     son = new int[(const int)(n + 1)];
 91     for(int i = 0;i <= n;i++){
 92         son[i] = n + 1;
 93         bro[i] = n + 1;
 94     }
 95     for(int i = 1;i <= n;i++){
 96         for(int j = head[i];j;j = edge[j].next){
 97             if(belong[i] == i && belong[i] != belong[edge[j].end]){
 98                 bro[i] = son[belong[edge[j].end]];
 99                 son[belong[edge[j].end]] = i;
100             }
101         }
102     }
103 }
104 int f[102][501];
105 void solve(int index){
106     if(index > n) return ;
107     solve(son[index]);
108     solve(bro[index]);
109     int left = son[index];
110     int right = bro[index];
111     for(int i = 1;i <= m;i++){
112         f[index][i] = max(f[index][i],f[right][i]);
113         int limit = i - w[index];
114         for(int j = 0;j <= limit;j++){
115             f[index][i] = max(f[index][i],v[index] + f[left][j] + f[right][limit - j]);
116         }
117     }
118 } 
119 int main(){
120     cin>>n>>m;
121     head=new int[(const int)(n+1)];
122     edge=new Edge[(const int)(n+1)];
123     visited=new boolean[(const int)(n+1)];
124     visitID=new int[(const int)(n+1)];
125     exitID =new int[(const int)(n+1)];
126     belong =new int[(const int)(n+1)];
127     inStack=new boolean[(const int)(n+1)];
128     memset(head,0,sizeof(int)*(n+1));
129     memset(visited,false,sizeof(boolean)*(n+1));
130     memset(inStack,false,sizeof(boolean)*(n+1));
131     w = new int[(const int)(n + 1)];
132     v = new int[(const int)(n + 1)];
133     d = new int[(const int)(n + 1)];
134     for(int i=1;i<=n;i++)
135         scanf("%d",&w[i]);
136     for(int i = 1;i <= n;i++)
137         scanf("%d",&v[i]);
138     for(int i = 1;i <= n;i++){
139         scanf("%d",&d[i]);
140         addEdge(i, d[i]);
141     }
142     for(int i=0;i<=n;i++) belong[i]=i;
143     for(int i=1;i<=n;i++){
144         if(!visited[i])
145             Tarjan(i);
146     }
147     delete[] visited;
148     delete[] inStack;
149     rebuild();
150     delete[] exitID;
151     delete[] visitID; 
152     create();
153     w[0] = 0;
154     v[0] = 0;
155     solve(0);
156     printf("%d",f[0][m]);
157     return 0;
158 }