洛谷P4322.最佳团体
题目大意
一个 \(n(1\leq n\leq 2500)\) 个节点的森林，每个点 \(i\) 有权值 \(s_{i},p_{i}(0
思路
这很显然是一个分数规划问题，我们可以让每个节点 \(i\) 的权值为 \(p_{i}-s_{i}\times mid\) ，然后二分来判断。我们用节点 \(0\) 作为根把所有森林连起来变成一棵树，每次判断时作树形 \(dp\) ，设 \(dp[v,i]\) 为在以 \(v\) 为根的子树中选取了 \(i\) 个点所获得的最大权值，于是在合并子树 \(to\) 的过程中，有：
\[dp[v,j+k]=max(dp[v,j+k],dp[v,j]+dp[to,k])_{0\leq j每次 \(dp\) 时将所有 \(dp[v,0]\) 初始为 \(0\) ，其余为 \(-inf\) 。最后根据 \(dp[0,k]\) 是否 \(\geq0\) 来判断即可，每次 \(check\) 可以 \(O(n^2)\) 完成，因为每两个节点 \(x,y\) 仅会在 \(lca(x,y)\) 处对遍历次数产生 \(1\) 的贡献，复杂度 \(O(n^2logn)\) 。
代码
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 2510;
vectorG[maxn];
LL K, N, S[maxn], P[maxn], R[maxn];
double dp[maxn][maxn];
double val[maxn];
LL vsize[maxn];
void add_edge(int from, int to)
{
G[from].push_back(to);
}
void dfs(int v)
{
vsize[v] = 1;
dp[v][0] = 0;
if (!G[v].size())
{
dp[v][1] = val[v];
return;
}
for (int i = 0; i < G[v].size(); i++)
{
int to = G[v][i];
dfs(to);
for (int j = vsize[v] - 1; j >= 0; j--)
{
for (int k = vsize[to]; k >= 0; k--)
dp[v][j + k] = max(dp[v][j + k], dp[v][j] + dp[to][k]);
}
vsize[v] += vsize[to];
}
if (v)
{
for (int i = vsize[v]; i > 0; i--)
dp[v][i] = dp[v][i - 1] + val[v];
}
}
bool check(double x)
{
for (int i = 0; i <= N; i++)
{
for (int j = 1; j <= K; j++)
dp[i][j] = -inf;
}
for (int i = 1; i <= N; i++)
val[i] = P[i] - S[i] * x;
dfs(0);
if (dp[0][K] - 0 > -eps)
return true;
return false;
}
void solve()
{
double lo = 0, hi = inf;
for (int i = 1; i <= 100; i++)
{
double mid = (lo + hi) / 2;
if (check(mid))
lo = mid;
else
hi = mid;
}
cout << setiosflags(ios::fixed) << setprecision(3) << lo << endl;
}
int main()
{
IOS;
cin >> K >> N;
for (int i = 1; i <= N; i++)
{
cin >> S[i] >> P[i] >> R[i];
add_edge(R[i], i);
}
solve();
return 0;
}