题意:01分数规划,但可选的数字之间存在森林形的依赖关系(可以认为0号点是个虚根,因为并不能选).
虽然有森林形的依赖关系，但还是可以套分数规划的思路,二分答案k,判断是否存在一个比值大于k的方案
即是否存在一种选取方式使得sigma{fight[i],i is choosed}/sigma{cost[i],i is choosed}>=k
移项,发现只需要sigma{fight[i]-cost[i]*k,i is choosed}>=0,也就是把每个点的权值设置成”战斗力-花费*比值”,判断是否存在一种满足依赖关系的选取方案使得选择的权值之和>=0,那么让权值之和尽量大判定最大值是否大于等于0即可.定义f[i][j]表示i为根的子树中选取j个点时的最大权值,用背包暴力转移,看似是O(n^3)的,但仔细分析发现复杂度是O(n^2)的,因为每次合并一棵子树时付出的代价是”已经合并的兄弟子树的大小之和”*”正在合并的这棵子树的大小”,实质上是树上每对节点在LCA处贡献时间复杂度,这一部分相当于bzoj4033.
于是总体复杂度是O (log(ans)*N^2),n是2500,感觉很虚但是能跑过去…注意处理某棵子树如果选择那么子树的根节点必须选择,以及0号节点的处理.再有就是二分精度一定要调好.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct edge{
int to,next;
}lst[maxn];int first[maxn],len=;
void addedge(int a,int b){
lst[len].to=b;lst[len].next=first[a];first[a]=len++;
}
int k,n;
int cost[maxn],fight[maxn],prt[maxn],sz[maxn];
double w[maxn];
double f[maxn][maxn];
void dfs(int x){
sz[x]=;
for(int pt=first[x];pt;pt=lst[pt].next){
dfs(lst[pt].to);
sz[x]+=sz[lst[pt].to];
}
}
void dp(int x){
int tot=;
if(x)f[x][]=w[x],tot=;
else f[x][]=;
for(int pt=first[x];pt;pt=lst[pt].next){
dp(lst[pt].to);tot+=sz[lst[pt].to];
for(int i=tot;i>=;--i){
for(int j=;j<=sz[lst[pt].to]&&j<=i;++j){
f[x][i]=max(f[x][i],f[x][i-j]+f[lst[pt].to][j]);
}
}
} }
bool check(double ans){
for(int i=;i<=n;++i){
w[i]=fight[i]-ans*cost[i];
}
memset(f,0xc2,sizeof(f));
dp();//printf("%.3f\n",f[2][1]);
return f[][k]>=;
}
int main(){
scanf("%d%d",&k,&n);
for(int i=;i<=n;++i){
scanf("%d%d%d",&cost[i],&fight[i],&prt[i]);addedge(prt[i],i);
}
dfs();
double l=,r=1e4;
while(r-l>1e-){
double mid=(l+r)/;
if(check(mid))l=mid;
else r=mid;
}
printf("%.3f\n",(r+l)/);
return ;
}