LuoGuP4322[JSOI2016]最佳团体

Posted on |

Problem

传送门

给一颗树，每个节点有两个权值$a_i,b_i$。

要求选出k个节点，使$\frac{\sum{a_i}}{\sum{b_i}}$尽可能大。

限制条件：当且仅当该点的父亲已经被选择时才可以选择这个节点。

$n\leq2500$

Solution

最近右边大佬学了分数规划，怒A五道神题后热血沸腾的向我详细讲了分数规划的实现。

基本实现大概是这样的：

假设我们知道答案，那么原式子可以化成：

所以我们只需先二分答案，再给每个物品附一个权值$v_i=a_i-b_i*ans$然后判断能否选出k个物品使$\sum v_i>0$即可。

这道题的话……只是多套一个树形依赖背包就可以了。

反正每写过树形依赖背包的博客，就在这讲一下吧……

设$dp_{i,j}$表示以i为根的子树内选择j个点的最优解。

转移的话……对于每个儿子节点，枚举从儿子的子树中选择多少个节点，直接转移即可。

也可以像右边大佬一样用下面的式子转移

其中$sz[i]$为$i$的子树大小。

最后的答案为$dp[0][m+1]$关于为什么是这个……请看原题面

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 3e3;
int s[Maxn], p[Maxn], root, n, m, sum, siz[Maxn];
double dp[Maxn][Maxn], val[Maxn], tmp[Maxn];
vector <int> g[Maxn];
double eps = 1e-6;
void dfs(int now, int pa){
	siz[now] = 1;
	dp[now][1] = val[now];
	for (int i = g[now].size() - 1; i >= 0; --i){
		int nxt = g[now][i];
		if(nxt == pa) continue;
		dfs(nxt, now);
		for (int j = 1; j <= siz[nxt] + siz[now]; ++j) tmp[j] = -1e9;
		for (int j = 1; j <= siz[now]; ++j)
			for (int k = 0, q = min(siz[nxt], m - j + 1); k <= q; ++k) 
				tmp[j + k] = max(tmp[j + k], dp[nxt][k] + dp[now][j]);
		siz[now] += siz[nxt];
		for (int j = 1; j <= siz[now]; ++j) dp[now][j] = tmp[j];
	}
}
bool solve(double d){
	for (int i = 1; i <= n; ++i) val[i] = 1.00 * p[i] - 1.00 * d * s[i];
	dfs(root, 0);
	if(dp[root][m + 1] > 0) return 1;
	else return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	m = read(), n = read(), sum = 0;
	for (int i = 1; i <= n; ++i){
		s[i] = read(), p[i] = read();
		sum += p[i];
		int r = read();
		g[r].push_back(i);
	}
	root = 0;
	double l, r = sum;
	while(r - l > eps){
		double mid = (r + l) / 2;
		if(solve(mid)) l = mid + eps;
		else r = mid - eps;
	}
	printf("%.3lf\n", l);
	return 0;
}