题意
题目链接
给一棵树，选取叶节点一次需要花费\(w_i\)代价，获得\(v_i\)收益，一个叶子节点最多选择\(l_i\)次，非叶子节点也有收益\(v_i\)，它由其叶子节点按照一定比例混合得来。问花费为\(m\)所能获得的最大收益
思路
神仙树形dp
首先看出来是树形dp，之后就一定是树上背包啦~~~
设\(f[i][j][k]\)表示在\(i\)号节点，向父亲传\(j\)次，且\(i\)子树共花费了\(k\)代价的最大收益
先枚举当前节点的选取次数\(l\)
用\(g[i][j]\)表示考虑了当前子树的前\(i\)个儿子，且它们总花费代价为\(j\)的最大收益，转移方程为\(g[i][j]=max(g[i-1][j-k]+f[v][l*e][k])\)，得到\(g[tot][j]\)（即所有儿子，其中e为v儿子转换成父亲的比例）
再枚举当前节点向父亲传的次数\(j\)
有\(f[rt][j][k]=max(g[tot][k]+v[rt]*(l-j))\)
另外，由于可能不止一棵树，需要用背包对森林进行合并，这个操作和01背包相同
Code
#include<bits/stdc++.h>
#define N 55
#define M 2005
#define Max(x,y) ((x)>(y) ? (x):(y))
using namespace std;
int n,m;
int S[N],W[N],L[N];//力量，价格，数量
int rd[N];
int f[N][105][M];//在i节点选择j个上传，子树花费k代价的总力量值
int ans[M],g[N][M],tot;
struct Edge
{
int next,to,val;//val是使用次数
}edge[N*N];int head[N],cnt;
void add_edge(int from,int to,int val)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].val=val;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void dfs(int rt)//处理rt子树
{
if(!head[rt])//叶子
{
L[rt]=min(L[rt],m/W[rt]);
for(int i=0;i<=L[rt];++i)
for(int j=0;j<=i;++j)
f[rt][j][i*W[rt]]=(i-j)*S[rt];
return;
}
L[rt]=100000000;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
dfs(v);
L[rt]=min(L[rt],L[v]/edge[i].val);//判边界
W[rt]+=W[v]*edge[i].val;
}
L[rt]=min(L[rt],m/W[rt]);//神装限制数量
memset(g,-50,sizeof(g));
g[0][0]=0;
for(int l=L[rt];l>=0;--l)
{
tot=0;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
++tot;
for(int j=0;j<=m;++j)//前tot个儿子共花费j
for(int k=0;k<=j;++k)//前tot-1个花费k
{
g[tot][j]=Max(g[tot][j],g[tot-1][k]+f[v][l*edge[i].val][j-k]);
}
}
for(int j=0;j<=l;++j)//上传j个
for(int k=0;k<=m;++k)
f[rt][j][k]=Max(f[rt][j][k],g[tot][k]+S[rt]*(l-j));
}
}
int main()
{
memset(f,-50,sizeof(f));
read(n);read(m);
for(int i=1;i<=n;++i)
{
char op[2];
read(S[i]);
scanf("%s",op);
if(op[0]=='A')//神装
{
int c; read(c);
for(int j=1;j<=c;++j)
{
int x; read(x);
int p; read(p);
add_edge(i,x,p);
++rd[x];
}
}
else read(W[i]),read(L[i]);
}
for(int i=1;i<=n;++i)
{
if(!rd[i])
{
dfs(i);
for(int k=m;k>=0;--k)
for(int j=0;j<=k;++j)
ans[k]=Max(ans[k],ans[k-j]+f[i][0][j]);
}
}
cout<<ans[m]<<endl;
return 0;
}
转载于:https://www.cnblogs.com/Chtholly/p/11431819.html
相关资源：JAVA上百实例源码以及开源项目
