如果不考虑依赖关系环的话本题可以得到40分
具体做法就是在树上做一次背包dp.引用<背包九讲>的泛化物品概念,物品本身可以视作一个weight对应value的函数.只要枚举为每件物品提供的weight后取最优即可.本题中’物品’指的就是树上的一颗子树
接着考虑依赖关系环的问题.对于一个环要么全部取走,获得全部价值和,消耗全部费用和 ; 要么一个都不取.显然这里应该tarjan缩点.因为保证每个点的入度为1,所以一个环缩点之后一定是树上的根.最后将森林上的每个根都挂向0节点,形成一颗树即可
代码如下.蒻的英语不好请见谅
//by:beautyyu
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ull unsigned long long
using namespace std;
struct edge
{
int v, nxt;
}e[5000];
int head[5000],memf[5000][1000],memd[5000][1000];
//'memd' -- memory for function 'd','memf' -- memory for function 'f'
int w[5000],v[5000];
int d(int al,int be);
int f(int al,int be);
//tarjan begin
int sta[5000],top = 0;bool insta[5000];//stack
int dfn[5000],low[5000],bl[5000],bcnt = 0,c = 0;
void tarjan(int k){
dfn[k] = low[k] = ++ c;
insta[sta[++ top] = k] = 1;
for (int i = head[k];i;i = e[i].nxt){
int &ev = e[i].v;
if (!dfn[ev]){
tarjan(ev);
low[k] = min(low[k],low[ev]);
}
else if (insta[ev])
low[k] = min(low[k],dfn[ev]);
}
if (low[k] == dfn[k]){
++ bcnt;
do insta[sta[top]] = 0,bl[sta[top --]] = bcnt;
while(sta[top + 1] != k);
}
return ;
}
//tarjan end
int main (){
int n,m;
//read gragh
cin >> n >> m;
int de[5000],be[5000],ge[5000];
for (int i = 1;i <= n;++ i)
scanf("%d",&de[i]);
for (int i = 1;i <= n;++ i)
scanf("%d",&be[i]);
int al,cnt = 0;
for (int i = 1;i <= n;++ i){
scanf("%d",&al);
ge[i] = al;
e[++ cnt] = edge{i,head[al]};
head[al] = cnt;
}
//read gragh end
for (int i = 1;i <= n;++ i)
if(!dfn[i]) tarjan(i);
//build new tree
for (int i = 1;i <= n;++ i)
w[bl[i]] += de[i],
v[bl[i]] += be[i];
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
cnt = 0;
bool havefather[5000];
for (int i = 1;i <= n;++ i)
if (bl[i] != bl[ge[i]])
e[++ cnt] = edge{bl[i],head[bl[ge[i]]]},
head[bl[ge[i]]] = cnt,
havefather[bl[i]] = 1;
n = bcnt;
for (int i = 1;i <= n;++ i)
if(!havefather[i])
e[++ cnt] = edge{i,head[0]},
head[0] = cnt;
//build new tree end
memset(memd,-1,sizeof(memd));
memset(memf,-1,sizeof(memf));
memset(memf[0],0,sizeof(memf[0]));
cout << d(0,m);
return 0;
}
int d(int rt,int wei){
//most value porduced by the tree 'rt' with weight'wei'
if (memd[rt][wei] != -1) return memd[rt][wei];
if (wei < w[rt]) return memd[rt][wei] = 0;
return memd[rt][wei] = f(head[rt],wei - w[rt]) + v[rt];
}
int f(int i,int wei){
//most value porduced by the list begins from 'i' with weight'wei'
if (memf[i][wei] != -1) return memf[i][wei];
int ev = e[i].v;
int ans = 0;
for (int j = 0;j <= wei;++ j)
ans = max(ans,d(ev,j) + f(e[i].nxt,wei - j));
return memf[i][wei] = ans;
}