题目来源NAIPC 2016 或 [Jsoi2016]最佳团体,你会发现这俩题完全一致…

(听说是那段时间jsoi就是汉化国外的题目)

题目链接:http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006280

https://nanti.jisuanke.com/t/A2026

https://www.lydsy.com/JudgeOnline/problem.php?id=4753

题意是说有$n+1$个人,$0$号是CEO,$1$到$n$号是参选员工,每个员工$i$给一个薪水$s$和生产力$p$,还有一个推荐他的人的编号$r(0\le r < i)$,现在要选出$k$个员工,如果选了某个员工那么他的推荐人也必须选(除非他的推荐人是CEO),使得选出$k$个员工的生产力之和除以薪水之和最大。

做法:$n+1$个人实际构成了一个树,CEO是根。首先01分数规划模型很显然,那么二分答案$mid$,新的点权为$p_i-s_i\times mid$,现在要求树上$k+1$个点的连通块(包括根)的最大点权和。

经典背包型dp,$dp[i][j]$表示以$i$为根的联通块大小为$j$的最大点权和,最后求出$dp[0][k+1]$小于$0$说明二分出来的值比答案大了,反之说明小了。

直观上看二维的状态,转移还需要枚举新加的一个子树选多少的点,这样似乎上是$O(N^3)$,会超时?

实际上,我们每次只for到子树大小,可以证明这样时间复杂度是$O(N^2)$。直接看图理解吧:

意思就是说这样的写法等价于枚举所有的点对$(x,y)$的时间。所以最终这道题的时间复杂度为$O(N^2\log{C})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define N 2550
const double INF=1e99;
int k,n;
int num[N],a[N],b[N];
double dp[N][N],c[N],now[N];
vector<int> e[N];

void dfs(int u,int f)
{
double tmp[N];
tmp[0]=c[u];
num[u]=0;
for(auto &v:e[u])
{
if(v==f)continue;
dfs(v,u);
for(int i=0;i<=num[u]+num[v];i++)
now[i]=-INF;
for(int i=0;i<=num[u];i++)
for(int j=0;j<=num[v];j++)
now[i+j]=max(now[i+j],tmp[i]+dp[v][j]);
for(int i=0;i<=num[u]+num[v];i++)
tmp[i]=now[i];
num[u]+=num[v];
}
num[u]++;
dp[u][0]=0;
for(int i=1;i<=num[u];i++)
dp[u][i]=tmp[i-1];
}
double calc(double mid)
{
c[0]=0;
for(int i=1;i<=n;++i) c[i]=a[i]-mid*b[i];
dfs(0,-1);
return dp[0][k+1];
}
int main()
{
scanf("%d%d",&k,&n);
for(int i=1;i<=n;++i)
{
int fa;
scanf("%d%d%d",b+i,a+i,&fa);
e[fa].push_back(i);
}
double l=0,r=10000;
for(int i=1;i<=50;++i)
{
double mid=(l+r)/2;
if(calc(mid)>=0) l=mid;
else r=mid;
}
printf("%.3f\n",l);
return 0;
}