Luogu

分析

二分答案 $mid$。考虑 check()

$$ \frac{\sum p_i}{\sum s_i}>mid\Longrightarrow\sum(p_i-mid\times s_i)>0 $$

将 $p_i-mid\times s_i$ 作为价值跑树形背包即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2500+10;

int n,k,s[N],p[N];

struct edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

double w[N],dp[N][N],tmp[N]; int sz[N];
inline void dfs(int u) {
    dp[u][1]=w[u],sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v);
        for (re int j=0;j<=k;++j) tmp[j]=-1e18;
        for (re int j=1;j<=sz[u];++j)
            for (re int l=1;l<=min(sz[v],k-j);++l)
                tmp[j+l]=max(tmp[j+l],dp[u][j]+dp[v][l]);
        for (re int j=0;j<=k;++j) dp[u][j]=max(dp[u][j],tmp[j]);
        sz[u]+=sz[v];
    }
}

inline int check(double mid) {
    for (re int i=0;i<=n;++i)
        for (re int j=0;j<=k;++j) dp[i][j]=-1e18;
    for (re int i=1;i<=n;++i) w[i]=p[i]-mid*s[i];
    dfs(0); return dp[0][k]>0;
}

int main() {
    k=read()+1,n=read();
    for (re int i=1;i<=n;++i)
        s[i]=read(),p[i]=read(),addEdge(read(),i);
    double L=0,R=1e4;
    while (R-L>1e-4) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    printf("%.3f\n",L);
    return 0;
}
最后修改:2020 年 02 月 28 日 05 : 03 PM