本文共 1009 字，大约阅读时间需要 3 分钟。
分析
我们不难发现这是一棵树
于是01分数规划然后树上dp即可
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int n,m;int s[5000],p[5000],r[5000],siz[2505];double dp[2505][2505];vector v[5000];inline void go(int x,double mid){ dp[x][1]=double(p[x]-s[x]*mid); siz[x]=1; for(int i=0;i 0;j--) for(int k=0;k<=siz[v[x][i]];k++) dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[v[x][i]][k]); siz[x]+=siz[v[x][i]]; }}inline bool ck(double mid){ memset(dp,-10,sizeof(dp)); s[0]=p[0]=0; go(0,mid); return dp[0][m+1]>=0;}signed main(){ int i,j,k; scanf("%d%d",&m,&n); for(i=1;i<=n;i++){ scanf("%d%d%d",&s[i],&p[i],&r[i]); v[r[i]].push_back(i); } double le=0,ri=10000.0001; while(ri-le>0.0001){ double mid=(le+ri)/2; if(ck(mid))le=mid; else ri=mid; } printf("%0.3lf\n",le); return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/10357483.html