记录编号	600588	评测结果	AAAAAAAAAA
题目名称	[JSOI 2016]最佳团体	最终得分	100
用户昵称	zjzhe	是否通过	通过
代码语言	C++	运行时间	0.941 s
提交时间	2025-05-08 14:05:19	内存使用	15.25 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2515;
const double eps=1e-5;
int k,n,s[N],p[N],r[N],siz[N];
double c[N],f[N][N];
vector<int>lk[N];
void dfs(int u,int fa){
    siz[u]=1,f[u][1]=c[u];
    for(int v:lk[u]){
        if(v==fa)continue;
        dfs(v,u),siz[u]+=siz[v];
        for(int i=min(k+1,siz[u]);i>=1;i--){
            for(int j=0;j<=min(i-1,siz[v]);j++){
                f[u][i]=max(f[u][i],f[v][j]+f[u][i-j]);
            }
        }
    }
}
int check(double x){
    for(int i=1;i<=n;i++)c[i]=(double)p[i]-x*s[i];
    for(int i=0;i<=n;i++)for(int j=1;j<=k+1;j++)f[i][j]=-1e9;
    dfs(0,-1);
    return f[0][k+1]>0;
}
#undef int
int main(){
#define int long long
    freopen("bestteam.in","r",stdin);
    freopen("bestteam.out","w",stdout);
    cin>>k>>n;
    for(int i=1;i<=n;i++)cin>>s[i]>>p[i]>>r[i],lk[r[i]].push_back(i);
    double l=0,r=1e5,ans=0;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid))ans=mid,l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(3)<<ans;
    return 0;
}