【BZOJ】4753: [Jsoi2016]最佳团体 01分数规划+树上背包

时间:2022-10-03 03:39:04

【题意】n个人,每个人有价值ai和代价bi和一个依赖对象ri<i,选择 i 时 ri 也必须选择(ri=0时不依赖),求选择k个人使得Σai/Σbi最大。n<=2500,ai,bi<=1e4。

【算法】01分数规划+树上背包

【题解】首先二分答案ans,根据01分数规划赋新的权值ci=ai-ans*bi,转化为是否能在树上找k个点使得权值和>=0。

设f[i][j]表示子树 i 选择 j 个点的最大权值和,然后做树上背包即可。

注意:第一维从大到小枚举j,第二维枚举儿子背包。这个背包比较特殊,是因为一批物品只能也必须取一个

两个节点只在它们LCA处计算一次,所以只要背包不枚举满,均摊复杂度就是N^2。

总复杂度O(n^2*log ai)。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
const double inf=-; int first[maxn],n,K,a[maxn],b[maxn],tot,sz[maxn];
double f[maxn][maxn],c[maxn];
struct edge{int v,from;}e[maxn];
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
double max(double a,double b){return a<b?b:a;}
void dfs(int x){
for(int i=;i<=K;i++)f[x][i]=inf;
if(x)f[x][]=c[x],sz[x]=;else f[x][]=;
for(int i=first[x];i;i=e[i].from){
dfs(e[i].v);sz[x]+=sz[e[i].v];
for(int k=min(K,sz[x]);k>=;k--)//
for(int j=min(k-(x!=),sz[e[i].v]);j>=;j--)if(f[x][k-j]>inf+){
f[x][k]=max(f[x][k],f[x][k-j]+f[e[i].v][j]);
}else break;
}
}
bool solve(double ans){
for(int i=;i<=n;i++)c[i]=1.0*a[i]-ans*b[i];
dfs();
return f[][K]>=;
}
int main(){
scanf("%d%d",&K,&n);
double l=,r=,mid;
for(int i=;i<=n;i++){
int fa;
scanf("%d%d%d",&b[i],&a[i],&fa);
insert(fa,i);
}
r=1e4;//?
while(r-l>1e-){
mid=(l+r)/;
if(solve(mid))l=mid;else r=mid;
}
printf("%.3lf",l);
return ;
}