传送门
个人认为本题是这道题的加强版,加强之处在于本题要用到背包类树形DP.所以不会背包类树形DP的话,可以先做这道题.也可以自行学习.
推荐的第一道题的题解
推荐的第二道题的题解
题意:N个人,1-N编号,每个人价值pi,费用si,推荐人ri,如果选了i,就必须要选择他的推荐人ri,ri可以等于零(编号为0的人是特殊的,它永远在团队中,且没有价值和费用),从这N个人中选出m个人(不包括编号0的人)构成一个团队,使得团队总价值与总费用的比值最大.
又看到了比值最大(小)问题,就想到了分数规划,理解清楚题意,列出我们要求的答案就是(frac{sum_{i=1}^{k}pi}{sum_{i=1}^{k}si})
想到了分数规划,就想到了要二分答案,直接二分mid,如果此次二分的值成立,即(frac{sum_{i=1}^{k}pi}{sum_{i=1}^{k}si}>=mid)
整理一下上式得(sum_{i=1}^{k} (pi-si*mid>=0))
所以每次check时,把每个人的价值更新为(pi-si*mid),题目就转换为了有N个人,已知每个人的价值,选出k个人使得价值和>=0,有没有看到背包的影子?
以上都是分数规划的思路的模板,现在我们来考虑这道题目的特殊之处,就是每个人都有唯一的推荐人ri,只有推荐人ri被选中,才能选择第i个人.
因为每个人都有唯一的推荐人ri,相当于树中每个节点最多只有一个父节点,又因为有0号节点这个特殊的点存在,所以N+1个节点构成了一棵以0号节点为根节点的树,还因为题目要求最优解,于是就想到了可以树形DP.
设f[x][i]表示在以x为根节点的子树中选择i个点能获得的最大价值(一般树形DP都是这样设的吧),不讲了.
P.S.不知道是本题卡常太过分,还是我的代码太丑,一定要吸氧才能不超时(这道题我交了几十遍,最好的成绩都T了一个点,欢迎各位不吸氧就能过的巨佬吊打教我)
int n,m;
int s[2505],p[2505],r[2505],size[2505];
double eps=1e-6;//设置二分精度
double v[2505],f[2505][2505];
vector<int> q[2505];
inline void dfs(int x){
f[x][0]=0;f[x][1]=v[x];
for(int i=2;i<=m;i++)f[x][i]=-1e9;
//初始化,这个很显然吧
size[x]=1;
//size数组表示以x为根节点的子树中的子节点的数量
//把x视作以x为根节点的子树中的子节点,所以初始值为1
//用于优化树形DP,不优化T飞5个点
//不懂的话,底下推荐的第二篇博客有提到
for(int i=0;i<q[x].size();i++){
int y=q[x][i];
dfs(y);
for(int j=size[x];j>=1;j--)
for(int k=0;k<=size[y];k++){
if(j+k>m)break;//优化
f[x][j+k]=max(f[x][j+k],f[x][j]+f[y][k]);
}
size[x]+=size[y];
}
}
inline bool check(double mid){
for(int i=1;i<=n;i++)
v[i]=p[i]-s[i]*mid;
//记得根据mid更新每个人的价值
dfs(0);//从根节点开始遍历整个树
return f[0][m]>=0;//判定
}
int main(){
m=read();n=read();
m++;
//因为0号节点必选,所以相当于我们要选择m+1个节点
for(int i=1;i<=n;i++){
s[i]=read();
p[i]=read();
r[i]=read();
q[r[i]].push_back(i);
}
//我直接vector存图了,也可以用链式前向星
double l=0,r=1e6,mid;
while(l+eps<r){
mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}
printf("%.3lf
",l);
return 0;
}
推荐1
推荐2