bzoj 4753 [Jsoi2016]最佳团体

bzoj 4753 [Jsoi2016]最佳团体

​​ Description JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。每个候选人都由一位 编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐，JYY需要保证， 如果招募了候选人i，那么候选人Ri”也一定需要在团队中。当然了，JYY自己总是在团队里的。每一个候选人都有 一个战斗值Pi”，也有一个招募费用Si”。JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。 也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。 Input 输入一行包含两个正整数K和N。 接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号。 对于100%的数据满足1≤K≤N≤2500,0< ” Si,Pi”≤10^4,0≤Ri< i Output 输出一行一个实数，表示最佳比值。答案保留三位小数。 Sample Input 1 2

1000 1 0

1 1000 1 Sample Output 0.001

HINT 2017.9.12新加数据一组 By GXZlegend

Source

分数规划+dfs序 背包 常数大 差点被卡T

二分答案 然后结果就是sigma p[x]-s[x]*mid

设dp[i][j]表示i子树选了j个点的最大代价

具体可上网搜索 依赖型背包

只要看选k个能否>0即可

#include#include#include#include#include#define eps 1e-9using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2550;struct node{ int y,next;}data[N<<1];double dp[N][N],mid;int num,h[N],k,n,s[N],p[N];inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;}inline void dfs(int x,int fa){ if (x) for (int i=k-1;~i;--i) dp[x][i+1]=dp[x][i]+p[x]-mid*s[x]; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (x==0) dp[y][0]=0; for (int j=1;j<=k;++j) dp[y][j]=dp[x][j];dfs(y,x); } for (int i=1;i<=k;++i) dp[fa][i]=max(dp[fa][i],dp[x][i]);}inline bool check(double md){ memset(dp,0xc2,sizeof(dp)); mid=md;dp[0][0]=0; dfs(0,0);return dp[0][k]>eps;}int main(){ freopen("bzoj4753.in","r",stdin); k=read();n=read(); for (int i=1;i<=n;++i){ s[i]=read();p[i]=read();int r=read(); insert1(r,i); } double l=0,r=2e7; while(fabs(r-l)>eps){ double md=(l+r)/2; if (check(md)) l=mid;else r=mid; }printf("%.3f\n",r); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。