分析
那么考虑二分答案,那么每个也就变成选择一群合法的招募人,使其和不少于0
然而O(n3)会超时
所以需要维护dfs序优化,时间复杂度O(n2)
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
const int N=2511;
struct node{int y,next;}e[N]; double p[N],dp[N][N];
int w[N],ls[N],c[N],dfn[N],ed[N],n,m,k,tot;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void add(int x,int y){
e[++k]=(node){y,ls[x]},ls[x]=k;
}
inline void dfs(int x){
dfn[x]=tot++;
for (rr int i=ls[x];~i;i=e[i].next)
dfs(e[i].y);
ed[dfn[x]]=tot;
}
inline bool check(double mid){
for (rr int i=1;i<=n;++i) p[dfn[i]]=c[i]-mid*w[i];
for (rr int i=1;i<=n+1;++i)
for (rr int j=0;j<=m+1;++j) dp[i][j]=-1e7;
for (rr int i=0;i<=n;++i)
for (rr int j=0;j<=m+1&&j<=i;++j){
if (dp[i][j]+p[i]>dp[i+1][j+1]) dp[i+1][j+1]=dp[i][j]+p[i];
if (dp[i][j]>dp[ed[i]][j]) dp[ed[i]][j]=dp[i][j];
}
return dp[n+1][m+1]>1e-5;
}
signed main(){
m=iut(); n=iut();
memset(ls,-1,sizeof(ls));
for (rr int i=1;i<=n;++i)
w[i]=iut(),c[i]=iut(),add(iut(),i);
dfs(0);
rr double l=0,r=10000;
while (l+1e-5<r){
rr double mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;
}
return !printf("%.3lf",l);
}