题解 P2515 【[HAOI2010]软件安装】
KevinYu
2018-11-28 21:12:22
这一题真是无限次苦苦挣扎得出的产物啊。
我们来一步步地分析题面:
1.这一道题乍一看像是一个树上背包的问题，我们于是得出程序的主要框架:树形dp。
我们先建图，用```up[i]```来存储i的先决条件(注意:x,i不要搞反了)。
```cpp
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
up[i]=x;
if(x!=0)addedge(x,i);
}
```
但是，题目描述中并没有说这个东西一定是一棵树,它有可能是一张带环图，也可能是一个森林。
例如，考虑这样的一个依赖关系:
```cpp
4 9
3 3 3 1
2 3 4 6
2 3 1 1
```
我们发现:这个图建完后是一个带环图。1，2，3号节点互为依赖条件。一旦有其中任何一个点没有被选择，整个环里面的所有内容都无法被使用。
我们重新观察这张图，我们发现1，2，3号节点的共性：我们可以对它整个选择，也可以对它整个不选择，对其中的任何一个真子集都没有意义。
对于环中点有共性的图，我们考虑用缩点来解决问题(本题中以tarjan算法为例)。
2.缩点过程(会tarjan的可以跳过):
tarjan算法基于时间戳与dfs实现，我们将一个点被发现的时间存入dfn数组中，然后将一个点够追溯到的最早的栈中节点的次序计入low数组中。
我们来过一遍算法流程：
1.初始化:
```cpp
void tarjan(int u)
{
low[u]=dfn[u]=++now;
hep[++top]=u;vis[u]=1;
```
我们可以发现，tarjan的初始化中要完成2个工作:
①.更新时间戳与low数组
②.将节点压栈并打上标记
2.tarjan主过程:
```cpp
for(int i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
```
我们来慢慢分析它：
我们首先遍历每一条边，然后对能到达的点进行访问:
```cpp
for(int i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
```
我们需要分出三种v点：
1.从没访问过的
对于这个点，我们将它作为下一个点，递归地进行tarjan过程。
在tarjan结束后，更新它的low数组。
你可以把更新的过程理解成从tarjan过程里回传来了它的low值，我们将它的low值与现在这个节点的low值比较，并取较小值。
```cpp
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
```
2.访问过，并在栈里的
这种节点是可以到达当前节点的，我们发现了这样一个点，就是发现了一个强连通分量，于是我们对当前点的low值进行更新
```cpp
else if(vis[v])low[u]=min(low[u],dfn[v]);
```
3.访问过，但不在栈里的
都不能到达你，跟你有什么关系吗，直接忽视掉就行了。
3.退栈:
```cpp
if(dfn[u]==low[u])
{
++tot;
vis[u]=0;
while(hep[top+1]!=u)
{
fa[hep[top]]=tot;
vis[hep[top--]]=0;
}
}
}
```
整个退栈过程就是记录强连通分量的过程，下面我就来详细解释一下。
退栈的条件是```dfn[u]==low[u]```，代表着我们的遍历过程已经触底，并且回溯回来了。
在我们当前点上方的都是什么点呢？都是在同一个强连通分量中的点。所以我们将其全部取出，并记录进一个强连通分量中(一般管这个叫“染色”)。
tarjan缩点过程完整代码:
```cpp
void tarjan(int u)
{
low[u]=dfn[u]=++now;
hep[++top]=u;vis[u]=1;
for(int i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++tot;
vis[u]=0;
while(hep[top+1]!=u)
{
fa[hep[top]]=tot;
vis[hep[top--]]=0;
}
}
}
```
3.重新建图:
我们通过缩点，将这个图变成一个有向无环图(树或森林)，我们需要重新建一个图(注意起点和终点的顺序):
```cpp
for(int i=1;i<=n;i++)
{
val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
if(fa[i]!=fa[up[i]]&&up[i]!=0)
{
addag(fa[up[i]],fa[i]);
usd[fa[i]]++;
}
}
```
我们为了将其转换成一棵树，将这个图每一个根节点都连到一个点上:
```cpp
int s=tot+1;
for(int i=1;i<=tot;i++)if(!usd[i])addag(s,i);
cost[s]=0;val[s]=0;
```
4.树形dp:
我们用dfs来描述dp过程
规定dfs(u)表示进行到了当前节点，```f[i][j]```代表当前节点是i，还剩j的空间。
算法流程如下:
1.初始化
```cpp
for(int i=cost[u];i<=m;i++)f[u][i]=val[u];
```
我们将每一个大于当前点花费的f数组初始化为u的价值。
2.遍历每一条边:
```cpp
for(int i=hag[u];i!=-1;i=dag[i].next)
{
int v=dag[i].to;
```
3.根据转移方程完成算法：
我们取了下一个点，并意识到：我们可以选当前点，也可以不选当前点，若不选当前点，其所有子节点都无法被选择。
依此我们得到状态转移方程：
```cpp
f[u][j+cost[u]]={max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);}
```
就是取子节点中的最优解，并加上当前节点的权值。
```cpp
dfs(v);
for(int j=m-cost[u];j>=0;j--)
{
for(int q=0;q<=j;q++)
{
f[u][j+cost[u]]=max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);
}
}
}
}
```
dfs过程就此结束。
完整代码:
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
struct edge
{
int to,next;
}a[1010],dag[1010];
int hag[1010];
int head[1010];
int v[1010];
int w[1010];
int cost[1010];
int val[1010];
int f[1010][5050];
int low[1010];
int dfn[1010];
int now(0);
int hep[1010];
int top(0);
int vis[1010];
int fa[1010];
int up[1010];
int usd[1010];
int cnt(0);
int cal(0);
int tot(0);
int n,m;
void addedge(int xi,int yi)
{
a[cnt].to=yi;
a[cnt].next=head[xi];
head[xi]=cnt++;
}
void addag(int xi,int yi)
{
dag[cal].to=yi;
dag[cal].next=hag[xi];
hag[xi]=cal++;
}
void tarjan(int u)
{
low[u]=dfn[u]=++now;
hep[++top]=u;vis[u]=1;
for(int i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++tot;
vis[u]=0;
while(hep[top+1]!=u)
{
fa[hep[top]]=tot;
vis[hep[top--]]=0;
}
}
}
void dfs(int u)
{
for(int i=cost[u];i<=m;i++)f[u][i]=val[u];
for(int i=hag[u];i!=-1;i=dag[i].next)
{
int v=dag[i].to;
dfs(v);
for(int j=m-cost[u];j>=0;j--)
{
for(int q=0;q<=j;q++)
{
f[u][j+cost[u]]=max(f[u][j+cost[u]],f[u][j+cost[u]-q]+f[v][q]);
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(hag,-1,sizeof(hag));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
up[i]=x;
if(x!=0)addedge(x,i);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
if(fa[i]!=fa[up[i]]&&up[i]!=0)
{
addag(fa[up[i]],fa[i]);
usd[fa[i]]++;
}
}
int s=tot+1;
for(int i=1;i<=tot;i++)if(!usd[i])addag(s,i);
cost[s]=0;val[s]=0;
dfs(s);
printf("%d",f[s][m+cost[s]]);
return 0;
}
```