记录编号	598093	评测结果	AAAAAAAAAA
题目名称	[JSOI 2016]最佳团体	最终得分	100
用户昵称	袁书杰	是否通过	通过
代码语言	C++	运行时间	0.745 s
提交时间	2025-01-05 10:53:59	内存使用	15.32 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int K,n,R[2505],head[2505*2],size[2505],etot;
double l,r,ans,a[2505],dp[2505][2505],s[2505],p[2505];
struct Edge {
	int u,v,nxt;
} e[2505*2];
void adde(int u,int v) {
	e[++etot]=(Edge) {
		u,v,head[u]
	};
	head[u]=etot;
}
void dfs(int now,int father,double num){
	if(now==0){
		dp[now][1]=0;
	}
	else{
		dp[now][1]=p[now]-num*s[now];
	}
	size[now]=1;
	for(int i=head[now];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==father){
			continue;
		}
		dfs(v,now,num);
		size[now]+=size[v];
		for(int j=min(size[now],K+1);j>=1;j--){
			for(int k=0;k<=min(size[v],j-1);k++){
				dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[v][k]);
			}
		}
	}
}
bool check(double num){
	for(int i=0;i<=n;i++){
		for(int j=1;j<=K+1;j++){
			dp[i][j]=-5e18;
		}
	}
	dfs(0,-1,num);
	return dp[0][K+1]>=0;
}
signed main(){
	freopen("bestteam.in","r",stdin);
	freopen("bestteam.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>K>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>p[i]>>R[i];
		adde(R[i],i);
	}
	r=1e4;
	while(r-l>1e-4){
		double mid=(l+r)/2;
		if(check(mid)){
			l=mid;
			ans=l;
		}
		else{
			r=mid;
		}
	}
	printf("%.3lf",ans);
	return 0;
}