JZdalao昨天上课讲的题目，话说JSOI的题目是真的不难，ZJOI的题目真的是虐啊！
题意很简单，抽象一下就是：有一棵树，一次只能选从根到某个节点上的链上的所有点，问从中取出k个节点所得到的总价值和总代价的比最大是多少。
像这种比值最大的题目，很容易让人联想到分数规划
关于分数规划的姿势，可以自行百度
对于题意进行进一步分析，得到要求的是：
max{∑v[i]/∑w[i]}(if i is chosen)
因此我们设x，二分x，看看是否存在：
max{∑v[i]/∑w[i]}>=x(if i is chosen)
移项得每个点的权值c[i]：
c[i]=v[i]-x*w[i](1<=i<=n)
所以我们得出c[i]，然后看看能否在树上找出满足题意的点集使得点权和大于等于0
所以要找出最大值，再考虑树形DP
但是一般的背包DP和多叉树转二叉树DP都是O(n^3)的
所以可以用DFS序来完成这种树上的n个点选m个点的DP
具体如下：
-
预处理出原树的DFS序，以及每个节点的子树大小
-
进行DP 用f[i][j]表示DFS序列中前i-1个点中选取j个点中得到的最大点权和
-
对于每一个f[i][j],可以转移：
-
f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+c[s[i]]) （选这个点）
-
f[i+size[s[i]]][j]=max(f[i+size[s[i]]][j],f[i][j]) （不选这个点,则直接跳过整棵子树）
最后判断f[n+1][k]是否大于等于0
注意这里的人数不包括根节点，因此k要加1
CODE
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
using namespace std;
typedef double DB;
const int N=2505;
const DB EPS=1e-5,INF=1e9;
struct edge
{
int to,next;
}e[N];
int head[N],v[N],w[N],size[N],s[N],n,k,x,cnt,tot;
DB f[N][N],c[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void DFS(int now)
{
s[++tot]=now; size[now]=1;
for (register int i=head[now];i!=-1;i=e[i].next)
DFS(e[i].to),size[now]+=size[e[i].to];
}
inline DB max(DB a,DB b)
{
return a>b?a:b;
}
inline bool check(DB x)
{
register int i,j;
for (i=1;i<=n;++i)
c[i]=(DB)v[i]-(DB)x*w[i];
for (i=1;i<=tot+1;++i)
for (j=0;j<=k;++j)
f[i][j]=-INF;
for (f[1][0]=0,i=1;i<=tot;++i)
for (j=0;j<=k;++j)
{
f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+c[s[i]]);
f[i+size[s[i]]][j]=max(f[i+size[s[i]]][j],f[i][j]);
}
return f[tot+1][k]>=0;
}
int main()
{
register int i;
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
read(k); read(n); ++k;
for (i=1;i<=n;++i)
{
read(w[i]); read(v[i]); read(x);
add(x,i);
}
DFS(0);
DB l=0,r=1e4;
while (r-l>EPS)
{
DB mid=(DB)(l+r)/2;
if (check(mid)) l=mid; else r=mid;
}
printf("%.3lf",l);
return 0;
}