[JSOI2016] 最佳团体

GitHub返回列表

OJ: luogu

题目 ID: P4322

标签: 分数规划树形DP

日期: 2026-01-07 09:17

目录

  1. 1. 题目结构对比
  2. 2. 解题步骤拆解
    1. 第一步：建树
    2. 第二步：01 分数规划 (套路)
    3. 第三步：树形背包 DP (Check 函数内部)
  3. 3. 代码实现的陷阱 (必看 ⚠️)
  4. 代码1
  5. 1. 为什么会 TLE？(未优化的时间复杂度)
    1. 🧮 算一笔账：
    2. 📉 总计算量：
  6. 2. sz 优化原理与复杂度 (Optimized Complexity)
    1. 🚀 为什么这会快？(数学证明)
    2. 📉 优化后的计算量：
  7. 3. 最终 AC 代码修改 (Copy This!)
  8. 总结
  9. 代码2: 优化后
P4322 最佳团体=P1642 规划 (01分数规划)+P2014 选课 (树形背包)\text{P4322 最佳团体} = \text{P1642 规划 (01分数规划)} + \text{P2014 选课 (树形背包)}

1. 题目结构对比

让我们把这道题和 P2014 选课 做个对比，你会发现它们是一模一样的：

特性 P2014 选课 P4322 最佳团体
依赖关系 选修课必须先修基础课 (父子关系) 招募人必须招募推荐人 (父子关系)
树的结构 森林 (连向虚拟根节点 0) 树 (JYY 是 0 号，也是根)
选择数量 选 MM 门课 选 KK 个候选人
目标 学分之和最大 总战斗值总费用\frac{\text{总战斗值}}{\text{总费用}} 最大
算法核心 纯树形背包 DP 二分答案 + 树形背包 DP

唯一的区别在于：

  1. 目标不同：选课是直接求和，最佳团体是求比值（所以要用 01 分数规划）。
  2. 数据范围：选课 N=300N=300，最佳团体 N=2500N=2500。这意味着你的 DP 写法必须非常优秀（必须加上我们之前讨论的 sz 剪枝优化），否则会超时。

2. 解题步骤拆解

第一步：建树

题目说“候选人 ii 由 RiR_i 推荐”，如果 Ri=0R_i=0 则是 JYY 推荐。

这说明 RiR_i 是 ii 的父节点。

  • Ri→iR_i \to i 连边。
  • 0 号节点（JYY）是整棵树的根。
  • 题目要求招募 KK 个人，算上 JYY 自己（0号点），我们实际上要在树上选 K+1K+1 个点。

第二步：01 分数规划 (套路)

假设最大性价比是 xx。

我们要判断：是否存在一种选法，使得 ∑Pi∑Si≥x\frac{\sum P_i}{\sum S_i} \ge x。

变形为：∑(Pi−x⋅Si)≥0\sum (P_i - x \cdot S_i) \ge 0。

Check 函数的逻辑：

  1. 给每个节点 ii 赋予新的权值：vali=Pi−x⋅Sival_i = P_i - x \cdot S_i。
  2. 特别地，JYY (0号点) 的 P0=0,S0=0P_0=0, S_0=0，所以 val0=0val_0 = 0。
  3. 问题转化为：在树上选 K+1K+1 个连通点（必须包含根），使得权值和最大。

第三步：树形背包 DP (Check 函数内部)

这和你在 P1642 写的一模一样：

  • dp[u][j]dp[u][j]：在 uu 的子树里选 jj 个点（含 uu）的最大权值。
  • 转移方程：分组背包，枚举分配给子树 vv 的点数 kk。
dp[u][j]=max⁡(dp[u][j],dp[u][j−k]+dp[v][k])dp[u][j] = \max(dp[u][j], \quad dp[u][j-k] + dp[v][k])

3. 代码实现的陷阱 (必看 ⚠️)

虽然逻辑简单，但这道题 N=2500N=2500，如果不加剪枝优化，复杂度是 O(N3)O(N^3) 或 O(N2⋅K)O(N^2 \cdot K)，即使是 O(N2)O(N^2) 在二分里跑 6060 次也非常危险（25002×60≈3.7×1082500^2 \times 60 \approx 3.7 \times 10^8）。

为了不超时，你必须严格遵守下面两点优化：

  1. 上下界剪枝：
    • 枚举 j 时，上限是 min(K+1, sz[u] + sz[v])。
    • 枚举 k 时，上限是 min(sz[v], j-1)。
    • 这就是你在 P1642 里学会的那个优化，在这里是必须的，它能保证树形背包的总复杂度严格是 O(N2)O(N^2)。
  2. 初始化细节：
    • dpdp 数组要初始化为 −∞-\infty。
    • dp[u][1]=valudp[u][1] = val_u。

代码1

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-07 09:17:48
 */
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const double  ninf = -1e10;

const int maxn = 2505;
const int maxe = 5005;
int n,m;
int K;
int a[maxn];
int S[maxn]; // 招募费用
int P[maxn]; // 战斗值
double dp[maxn][maxn]; // dp[u][i] 表示子树u选i个点的最大权值

//oisnip_beginlinklist_mini_struct.cpp
struct linkList {
    struct edge { int u, v,w, next; };
    edge e[maxe];
    int h[maxn], edge_cnt;
    linkList() { edge_cnt = 0; memset(h, -1, sizeof(h)); }
    void add(int u, int v,int w = 0) { e[edge_cnt] = {u, v,w, h[u]}; h[u] = edge_cnt++; }
    void add2(int u, int v,int w = 0) {
        add(u, v,w); add(v, u,w);
    }
} e;
//oisnip_end

void init(){
    std::cin >> K >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int s,p,r;
        std::cin >> s >> p >> r;
        e.add(r,i);
        S[i] = s;
        P[i] = p;
    }

}

void dfs_dp_tree(int u,double x) {

    if( u == 0) 
        dp[u][1] = 0;
    else 
        dp[u][1] = (double)P[u] - x * S[u];

    // 初始化
    for(int i = 2 ;i <= K+1 ;i++) dp[u][i] = ninf;

    for(int i = e.h[u] ; ~i ;i = e.e[i].next){
        int v = e.e[i].v;
        dfs_dp_tree(v,x);

        //无优化, 容量算到2就可以了
        for(int j = K+1; j>=2;j--) {

            // 分配给子树的容量,也是物品分组
            for(int k = 1 ;k <= j-1;k++) {
                if( dp[v][k] > ninf && dp[u][j-k] > ninf)
                    dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
            }
        }
    }
}

bool check(double x) {
    dfs_dp_tree(0,x);

    return  dp[0][K+1] >=0;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    //即使全是收益没有花费，最大值也就这么多
    double l  = 0, r= 10000;
    for(int i = 1;i <= 60 ;++i ) // i: 1->60
    {
        double mid = (l+r) /2;
        if( check(mid))
            l = mid; //成立
        else
            r = mid;
    }
    std::cout << fixed << setprecision(3) << l << "\n";
    
    return 0;
}

超时,有测试点TLE,原因 没有 sz[i] 数组优化

这完全符合预期！因为 N=2500N=2500 的数据范围对于 O(N3)O(N^3) 或者是 O(N⋅K2)O(N \cdot K^2) 的算法来说太大了。

你需要非常清楚地理解为什么会 TLE 以及 sz 优化为什么能救命。下面是详细的数学分析。

1. 为什么会 TLE？(未优化的时间复杂度)

你的当前代码中，DP 的合并部分是这样写的（伪代码逻辑）：

cpp
// 未优化的逻辑
for (int j = K + 1; j >= 2; j--) {       // 外层循环：常数 K
    for (int k = 1; k <= j - 1; k++) {   // 内层循环：常数 K
         // 状态转移 ...
    }
}

🧮 算一笔账：

  1. 二分外壳：循环 60 次。
  2. DP 遍历：树有 NN 个节点。
  3. 单次合并代价：
    • 在最坏情况下（比如树是一条链，或者 KK 很大接近 NN），对于每个节点 uu，你的两层循环基本上跑满了 K×KK \times K 次。
    • 也就是单次合并复杂度是 O(K2)O(K^2)。

📉 总计算量：

总操作数=二分次数×N×K2\text{总操作数} = \text{二分次数} \times N \times K^2

代入数据 N=2500,K=2500N=2500, K=2500：

60×2500×25002≈9.3×101160 \times 2500 \times 2500^2 \approx 9.3 \times 10^{11}

9300亿次运算！

目前的评测机，1秒钟大约能跑 10810^8 (1亿) 到 3×1083 \times 10^8 (3亿) 次运算。

你的代码需要跑 几千秒 才能跑完，所以必然 TLE。

2. sz 优化原理与复杂度 (Optimized Complexity)

加上 sz 优化后，代码变成了这样：

C++

cpp
// 优化后的逻辑
for (int j = min(K + 1, sz[u] + sz[v]); j >= 2; j--) { // 上限受限于当前子树大小
    for (int k = 1; k <= min(sz[v], j - 1); k++) {     // 上限受限于子节点大小
         // ...
    }
}
sz[u] += sz[v];

🚀 为什么这会快？(数学证明)

这个复杂度的证明非常经典，被称为 “树上点对贡献证明法”。

  1. 看内层的状态转移 dp[u][j-k] + dp[v][k]。
  2. 这本质上是将 子树 uu 中的任意一个节点 和 子树 vv 中的任意一个节点 进行配对计算。
  3. 对于整棵树中的任意两个节点 xx 和 yy：
    • 它们只会在它们的 最近公共祖先 (LCA) 处被合并一次。
    • 在 xx 和 yy 被合并到同一个父节点之前，它们在不同的子树里。
    • 在合并之后，它们属于同一个 sz，不会再被重新合并。
  4. 因此，树形背包的 DP 循环总执行次数，严格等同于树中点对 (x,y)(x, y) 的数量。

还不懂就去看: book/dynamic_programming/树形DP/树上分组背包sz优化原理与复杂度.md

📉 优化后的计算量：

树中任意两个点都可以组成一对，总点对数量是 CN2=N(N−1)2C_N^2 = \frac{N(N-1)}{2}，也就是 O(N2)O(N^2)。

考虑到我们有一个上限 KK，严格的复杂度是 O(N⋅K)O(N \cdot K)。但在最坏情况 K=NK=N 时，就是 O(N2)O(N^2)。

优化后总操作数=二分次数×N2\text{优化后总操作数} = \text{二分次数} \times N^2

代入数据 N=2500N=2500：

60×25002=60×6,250,000≈3.75×10860 \times 2500^2 = 60 \times 6,250,000 \approx 3.75 \times 10^8

3.75亿次运算。

虽然这个数字略微超过了 10810^8 的安全线，但因为 DP 内部的操作非常简单（只有加法和取 max，常数极小），且 N2N^2 是最坏情况（树要长得特定形状，且 KK 要很大），实际上它通常能在 1.2s - 1.5s 左右跑完，完全可以 AC。

3. 最终 AC 代码修改 (Copy This!)

你需要把 dfs_dp_tree 函数替换为下面的代码。重点看我标注 【关键优化】 的地方。

C++

void dfs_dp_tree(int u, double x) {
    // 1. 初始化 sz
    sz[u] = 1;

    if(u == 0) 
        dp[u][1] = 0;
    else 
        dp[u][1] = (double)P[u] - x * S[u];

    // 初始化其他状态
    for(int i = 2; i <= K + 1; i++) dp[u][i] = ninf;

    for(int i = e.h[u]; ~i; i = e.e[i].next) {
        int v = e.e[i].v;
        dfs_dp_tree(v, x);

        // 【关键优化 1】j 的上限取 min(K+1, sz[u] + sz[v])
        // 解释：我们不需要遍历到 K，只需要遍历到“目前总共拥有的节点数”
        for(int j = min(K + 1, sz[u] + sz[v]); j >= 2; j--) {
            
            // 【关键优化 2】k 的上限取 min(sz[v], j - 1)
            // 解释：子树 v 只有 sz[v] 个节点，不可能拿出更多
            for(int k = 1; k <= min(sz[v], j - 1); k++) {
                
                // 必须判断状态是否合法，防止 -inf + -inf 溢出或者逻辑错误
                if(dp[u][j - k] > ninf && dp[v][k] > ninf) {
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
                }
            }
        }
        // 【关键优化 3】合并完一个子树后，立刻更新当前子树大小
        sz[u] += sz[v];
    }
}

总结

  • 不优化：O(N⋅K2)≈1011O(N \cdot K^2) \approx 10^{11} →\to 必死无疑 (TLE)。
  • 优化：O(N2)≈108O(N^2) \approx 10^8 →\to 刚刚好 (AC)。

这就是为什么在 N>100N > 100 的树形背包题目中，sz 优化是必须写的标准套路。

代码2: 优化后

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-07 09:17:48
 */
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const double  ninf = -1e10;

const int maxn = 2505;
const int maxe = 5005;
int n,m;
int K;
int a[maxn];
int S[maxn]; // 招募费用
int P[maxn]; // 战斗值
double dp[maxn][maxn]; // dp[u][i] 表示子树u选i个点的最大权值
int sz[maxn]; //子树的大小

//oisnip_beginlinklist_mini_struct.cpp
struct linkList {
    struct edge { int u, v,w, next; };
    edge e[maxe];
    int h[maxn], edge_cnt;
    linkList() { edge_cnt = 0; memset(h, -1, sizeof(h)); }
    void add(int u, int v,int w = 0) { e[edge_cnt] = {u, v,w, h[u]}; h[u] = edge_cnt++; }
    void add2(int u, int v,int w = 0) {
        add(u, v,w); add(v, u,w);
    }
} e;
//oisnip_end

void init(){
    std::cin >> K >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int s,p,r;
        std::cin >> s >> p >> r;
        e.add(r,i);
        S[i] = s;
        P[i] = p;
    }

}

void dfs_dp_tree(int u,double x) {

    sz[u] = 1;
    if( u == 0) 
        dp[u][1] = 0;
    else 
        dp[u][1] = (double)P[u] - x * S[u];

    // 初始化
    for(int i = 2 ;i <= K+1 ;i++) dp[u][i] = ninf;

    for(int i = e.h[u] ; ~i ;i = e.e[i].next){
        int v = e.e[i].v;
        dfs_dp_tree(v,x);

        sz[u] += sz[v];
        //无优化, 容量算到2就可以了

        // 合并后的上限
        int J_UP = std::min(K+1, sz[u]);
        for(int j = J_UP; j>=2;j--) {

            int K_UP = std::min(sz[v],j-1);
            // 分配给子树的容量,也是物品分组
            for(int k = 1 ;k <= K_UP;k++) {
                if( dp[v][k] > ninf && dp[u][j-k] > ninf)
                    dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
            }
        }

    }
}

bool check(double x) {
    dfs_dp_tree(0,x);

    return  dp[0][K+1] >=0;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    //即使全是收益没有花费，最大值也就这么多
    double l  = 0, r= 10000;
    for(int i = 1;i <= 60 ;++i ) // i: 1->60
    {
        double mid = (l+r) /2;
        if( check(mid))
            l = mid; //成立
        else
            r = mid;
    }
    std::cout << fixed << setprecision(3) << l << "\n";
    
    return 0;
}