C++(g++ 7.5.0) 解法, 执行用时: 495ms, 内存消耗: 49700K, 提交时间: 2023-07-26 12:18:51

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

const double EPS=1e-4;
const int N=2505;
const int E=5005;

struct edge {int x,y,next;} e[E];

double f[N][N],tmp[N],v[N];
int size[N],a[N],b[N];
int ls[N],edCnt;

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,ls[y]}; ls[y]=edCnt;
}

void dfs(int now,int fa) {
	size[now]=1; f[now][0]=0; f[now][1]=v[now];
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y==fa) continue;
		dfs(e[i].y,now);
		rep(j,1,size[now]+size[e[i].y]) tmp[j]=f[0][N-1];
		rep(j,1,size[now]) rep(k,0,size[e[i].y]) {
			tmp[j+k]=std:: max(tmp[j+k],f[now][j]+f[e[i].y][k]);
		}
		size[now]+=size[e[i].y];
		rep(j,1,size[now]) f[now][j]=tmp[j];
	}
}

int main(void) {
	int n,m; scanf("%d%d",&m,&n);
	rep(i,1,n) {
		int fa; scanf("%d%d%d",&b[i],&a[i],&fa);
		add_edge(fa,i);
	}
	double l,r;
	for (l=0,r=10000;r-l>=EPS;) {
		double mid=(l+r)*0.5;
		fill(f,0xc2);
		rep(i,1,n) v[i]=(double)a[i]-mid*(double)b[i];
		dfs(0,0);
		if (f[0][m+1]>0) l=mid;
		else r=mid;
	}
	printf("%.3lf\n", l);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 813ms, 内存消耗: 75956K, 提交时间: 2020-01-30 13:24:12

#include<bits/stdc++.h>
using namespace std;
#define see(x) cerr<<(#x)<<"="<<x<<endl;
typedef long long ll;
const int N=3000+100;
const ll inf=1e18;
const double eps=1e-5;
ll v[N],c[N],n,k,siz[N];
vector<int>edge[N];
double mid,dp[N][N];

double dfs(int x) {
    siz[x]=1;
    dp[x][0]=0;
    dp[x][1]=(double)v[x]-(double)c[x]*mid;
    for(auto v:edge[x]) {
        dfs(v);
        for(int i=siz[x];i>=1;i--)
            for(int j=0;j<=siz[v];j++)
                dp[x][i+j]=max(dp[x][i+j],dp[x][i]+dp[v][j]);
        siz[x]+=siz[v];
    }
    if(x==0) return dp[x][k];
}

int main() {
    cin>>k>>n;k++;
    int x;
    for(int i=1;i<=n;i++) {
        scanf("%lld%lld%d",&c[i],&v[i],&x);
        edge[x].push_back(i);
    }
    double L=0,R=1e9,ans=0;
    while(L+eps<=R) {
        mid=(L+R)/2.0;
        memset(dp,-10,sizeof dp);
        if(dfs(0)>=0) ans=mid,L=mid;
        else R=mid;
    }
    printf("%.3f",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 887ms, 内存消耗: 50020K, 提交时间: 2020-03-28 15:44:48

#include<bits/stdc++.h>
using namespace std;


const int N=2510;
vector<int>G[N];


int sz[N];
double dp[N][N];

double p[N],s[N],tmp[N];

int n,k;
void dfs(int x,double mid)
{
	sz[x]=1;
	dp[x][0]=0;
	dp[x][1]=p[x]-s[x]*mid;
	for(int v:G[x])
	{
		dfs(v,mid);
		for(int i=0;i<=k;i++) tmp[i]=-0x3f3f3f3f;
		for(int i=1;i<=sz[x];i++)//父节点 必须要有 
		{
			for(int j=0;j<=sz[v]&&i+j<=k;j++)
			{
				tmp[i+j]=max(tmp[i+j],dp[x][i]+dp[v][j]);
			}
		}
		for(int i=0;i<=k;i++) dp[x][i]=max(dp[x][i],tmp[i]);
		sz[x]+=sz[v];
	}
}
int main()
{
	cin>>k>>n;
	k++;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>s[i]>>p[i]>>x;
		G[x].push_back(i);
	}
	double l=0,r=2e9;
	while(r-l>1e-5)
	{
		double mid=(l+r)/2;
		memset(dp,-0x3f,sizeof dp);
		dfs(0,mid);
		if(dp[0][k]>=0) l=mid;
		else r=mid-0.0001;
	}
	printf("%.3f\n",l);
	return 0; 
}