「JSOI 2016」最佳团体

发表于 | | 阅读次数:
字数统计: 750 字

Description

题目链接：BZOJ 4753

有 $N$ 名候选人，从 $1$ 到 $N$ 编号，队长编号为 $0$，每个候选人都由一位编号比他小的候选人推荐（如果为 $0$ 则表示是队长推荐的）。队长希望招募 $K$ 个人，但是他需要保证：如果招募了 $x$，那么他的推荐人也要招募（队长总是在团队里的）。每个人都有代价 $C_i$ 和价值 $W_i$ 两个值，招募可以获得的价值为 $\frac{\sum W_i}{\sum C_i}$，你需要最大化这个值，答案保留 $3$ 位小数。

数据范围：$1\le K\le N\le 2500$，$1\le C_i,W_i\le 10^4$

Solution

先做一个小转化：以 $0$ 为根节点，选择 $K+1$ 个点，其中根节点必须选择。

首先我们考虑树形 $\text{DP}$，显然是一道普通的树上背包问题。但是由于答案是一个比值，无法记录状态进行转移，所以我们引入 $01$ 分数规划。

这个式子显然是可以二分答案的，因此可以得到

由于分母是正数，我们将式子拆开

可得

故我们可以二分答案 $x$，将问题转化为：每个点有 $1$ 个属性 $P_i=W_i-x\times C_i$，能否使选取的点的属性和大于等于 $0$。

设计状态：$f[i][j]$ 表示在以第 $i$ 个节点为根的子树中，选择 $j$ 个节点的最大属性和。

$\text{DP}$ 为朴素的树上背包问题，转移非常显然（注意根节点 $i$ 对应的 $j$ 至少为 $1$，我就因为这个调试了半天）。

注意初始化：$f[i][0]=0$，$f[i][1]=W_i-x\times C_i$，其余状态的值均为无穷小。

时间复杂度：$O(N^2)​$（复杂度证明见 「HAOI 2015」树上染色）

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N=2505;
const double eps=1e-5;
int n,m,tot,c[N],s[N],hd[N],sz[N];
double w[N],f[N][N];
struct Edge{
    int to,nxt;
}e[N];
 
void add(int u,int v) {
    e[++tot].to=v;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
void dfs(int x) {
    sz[x]=1; f[x][1]=w[x];
    for(int i=hd[x];i;i=e[i].nxt) {
        int v=e[i].to; dfs(v);
        for(int j=sz[x];j>=1;--j)
            for(int k=0;k<=sz[v];++k)
                f[x][j+k]=max(f[x][j+k],f[x][j]+f[v][k]);
        sz[x]+=sz[v];
    }
}
bool check(double x) {
    memset(f,-10,sizeof(f));
    for(int i=0;i<=n;++i) f[i][0]=0;
    for(int i=1;i<=n;++i) w[i]=(double)s[i]-x*c[i];
    dfs(0);
    return f[0][m]>=0;
}
int main() {
    scanf("%d%d",&m,&n); ++m;
    for(int fa,i=1;i<=n;++i) {
        scanf("%d%d%d",&c[i],&s[i],&fa);
        add(fa,i);
    }
    double l=0,r=1e4,ans=0;
    while(l+eps<=r) {
        double mid=(l+r)/2;
        if(check(mid)) ans=mid,l=mid+eps; else r=mid-eps;
    }
    printf("%.3lf\n",ans);
    return 0;
}
0%