Bzoj4753 [jsoi2016]最佳团体

基础题加入实数炒冷饭

Posted by yjjr's blog on February 16, 2018

标签:二分,树形DP

题目

题目传送门

Description

JSOI信息学代表队一共有N名候选人,这些候选人从1到N编号。

方便起见,JYY的编号是0号。每个候选人都由一位编号比他小的候选人Ri推荐。

如果Ri=0则说明这个候选人是JYY自己看上的。

为了保证团队的和谐,JYY需要保证,如果招募了候选人i,那么候选人Ri”也一定需要在团队中。

当然了,JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi”,也有一个招募费用Si”。

JYY希望招募K个候选人(JYY自己不算),组成一个性价比最高的团队。

也就是,这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。

Input

输入一行包含两个正整数K和N。

接下来N行,其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用,战斗值和推荐人编号。

对于100%的数据满足1≤K≤N≤2500,0<”Si,Pi”≤10^4,0≤Ri<i

Output

输出一行一个实数,表示最佳比值。答案保留三位小数。

Sample Input

1 2

1000 1 0

1 1000 1

Sample Output

0.001

题意

给定一棵N个节点的树和每个节点的花费和战斗值,选定一个大小为K的联通块使得总战斗值和总费用比值最大

分析

二分答案,然后判断答案的可行性,剩下的就是一个树上的最优性背包

判断过程:

DP:f[i][j]表示以i节点为根的子树中选取j个点的最优权值

v数组表示战斗力-花费*比值x,g数组临时存放转移时的权值

常数略大,注意精度

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-6
#define inf 1e8
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=2e3+506;
struct edge{int to,next;}e[maxn<<1];
int last[maxn],n,k,size[maxn],w[maxn],c[maxn],cnt=0;
double f[maxn][maxn],g[maxn],v[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void build(double x){
	rep(i,0,n){
		v[i]=w[i]-x*c[i];
		rep(j,0,n)f[i][j]=-inf;
	}
}
void update(int x,int y){
	rep(i,0,size[x]+size[y])g[i]=-inf;
	rep(i,0,size[x])
		rep(j,0,size[y])g[i+j]=max(g[i+j],f[x][i]+f[y][j]);
	size[x]+=size[y];
	rep(i,0,size[x])f[x][i]=max(f[x][i],g[i]);
}
void dfs(int x){
	size[x]=0;f[x][0]=0;
	reg(x)dfs(e[i].to),update(x,e[i].to);
	dep(i,size[x],0)f[x][i+1]=f[x][i]+v[x];
	size[x]++;f[x][0]=0;
}
int main(){
	k=read(),n=read();k++;
	rep(i,1,n){
		c[i]=read(),w[i]=read();int x=read();
		insert(x,i);
	}
	double l=0,r=10000,ans;
	while(fabs(l-r)>eps){
		double mid=(l+r)/2;
		build(mid);dfs(0);
		if(f[0][k]>0)ans=mid,l=mid;else r=mid;
	}
	printf("%.3lf\n",ans);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr